我有一份家庭作业，我认为我已经解决了，但我不能完全确定，因为我无法证明我的解决方案。我想对我所做的、它的正确性以及是否有更好的解决方案发表评论。
问题如下:我们有 N 组人，其中组 i 有 g[i] 人。我们想将这些人分别放在两排 S 座位上，这样:每个组只能按连续顺序放在一行上，或者如果该组的成员数量为偶数，我们可以将它们分成两部分并放在两行中，但条件是它们必须形成一个矩形(因此它们必须在两行上具有相同的索引)。没有人站起来所需的最少座位数 S 是多少？
示例:组是 4 11。最小 S 为 11。我们将所有 4 放在一行，将 11 放在第二行。另:组为6 2。我们将 6 分成两行，也分为两行。因此，最少需要 4 个席位。
这是我的想法:
计算 T =(所有组的总和 + 1)/2。将组号存储在一个数组中，但将所有偶数 x 分成两个 x/2 值。所以 4 5 变成了 2 2 5。现在运行 subset sum在此向量上，找出大于或等于T的最小值可以组成。该值是每排所需的最少座位数。
示例:4 11 => 2 2 11 => T = (15 + 1)/2 = 8。我们可以从 2 2 11 中得出的最小值 >= 8 是 11，所以这就是答案。
这似乎可行，至少我找不到任何反例。虽然我没有证据。直觉上，似乎总是可以根据该算法提供的座位数，在所需条件下安排人员。
感谢任何提示。
最佳答案
我认为您的解决方案是正确的。最佳分布中每行的最少座位数就是您的 T(这在数学上很明显)。
拆分偶数也是正确的，因为它们有两种可能的排列；通过逻辑上将所有“矩形”人群放在一排座位的一端，您还可以保证他们将始终形成一个合适的矩形，从而也满足此条件。
所以问题归结为找到一个等于或尽可能接近 T 的总和(例如 partition problem )。
关于algorithm - 最佳安排人群，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5588707/