我有这个家庭作业,我认为我设法解决了,但我不能完全确定,因为我不能证明我的解决方案.我想评论我做了什么,它的正确性以及是否有更好的解决方案.
问题是:我们N的人,其中组群i拥有g[i]人在里面.我们希望将这些人分别放在两排S座位上,这样:每个组只能以连续的顺序放在一行上,或者如果该组具有偶数个成员,我们可以将它们分成两列,将它们放在两行上,但条件是它们必须形成一个矩形(因此它们必须在两行上具有相同的索引).S所需的最小座位数是多少,以便没有人站起来？
示例:组是4 11.最低S是11.我们将所有内容4放在一行中,然后11放在第二行中.另一个:团体6 2.我们拆分了6两行,还有两行.因此,最低4席位.
这就是我的想法:
计算T = (sum of all groups + 1) / 2.将组编号存储在一个数组中,但将所有偶数值拆分x为两个值x / 2.因此4 5变得2 2 5.现在在该向量上运行子集和,并找到高于或等于T可以形成的最小值.该值是每行所需的最小座位数.
示例:4 11 => 2 2 11 => T = (15 + 1) / 2 = 8.我们至少可以形成从2 2 11那>= 8就是11,所以这就是答案.
这似乎有效,至少我找不到任何反例.我没有证据.直观地说,似乎总是可以根据该算法提供的座位数在所需条件下安排人员.
任何提示都表示赞赏.