Optimization of optimal groups of people

Question

I have this homework, which, I think, I managed to solve, but I'm not entirely sure, because I can not prove my decision. I would like to receive comments about what I did, about its correctness and whether there is a better solution.

The problem is this: we have N groups of people, where group i has g[i] people in it. We want to put these people in two lines from S places each, so that: each group can only be placed on one line, in a continuous sequence, OR, if the group has an even number of members, we can split them into two and put them on two lines , but with the condition that they must form a rectangle (therefore, they must have the same indices on both rows). What is the minimum number of S seats required for no one to stand?

Example: Groups 4 11 . The minimum of S is 11 . We put all 4 on one line, and 11 on the second line. Other: groups 6 2 . We split 6 into two lines, as well as into two. So the minimum size is 4 .

That's what I think:

Calculate T = (sum of all groups + 1) / 2 . Store the group numbers in the array, but divide all the even x values ​​into two x / 2 values ​​each. So 4 5 becomes 2 2 5 . Now run the sum of the subset on this vector and find the minimum value greater than or equal to T that can be formed. This value is the minimum number of places in each row.

Example: 4 11 => 2 2 11 => T = (15 + 1) / 2 = 8 . We can form a minimum of 2 2 11 , which >= 8 - 11 , so the answer is.

This seems to work, at least I can't find a counter example. However, I have no evidence. It seems intuitively that you can always organize people in the required conditions with the number of places set by this algorithm.

Any hints appreciated.

Answer 1

I think your decision is correct. The minimum number of places in a row in the optimal distribution will be your T (which is mathematically obvious).

The division of even numbers is also true, since they have two possible measures; by logically placing all the “rectangular” groups of people at one end of the rows of seats, you can also ensure that they always form a regular rectangle, so that this condition also holds.

Thus, the question boils down to finding the sum equal to or as close as possible to T (for example, the partition problem ).

Answer 2

Minor thread: I'm not sure if the proposed solution above works in the boundary case where each group has 0 members, because your numerator in T = SUM ALL + 1 / 2 always positive, so there will never be a subset greater than or equal to T

To get around this, a module may work here. We know that we need at least n places in the line if n is the maximum odd term, therefore, perhaps the equation should have the term max(n * (n % 2)) . It will exit at max(odd) or 0. Since the maximum odd term is always added to S , I think it is safe (boldly said without proof ...).

Then we want to know whether even terms should be separated or not. Here, where a subset of the summary approach can be used, but with T just equal to SUM ALL / 2 .