StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p><strong>Never mind</strong>, I thought the numbers were sequential. This looks kind of like the <a href="http://en.wikipedia.org/wiki/Knapsack_problem" rel="nofollow noreferrer">Knapsack Problem</a>, which is NP hard.</p> <hr> <p>The numbers are sequential?</p> <ol> <li>Put the largest number in A</li> <li>Put the next largest number in B</li> <li>Put the next largest number in B</li> <li>Put the next largest number in A</li> <li>Repeat step 1 until all the numbers are assigned.</li> </ol> <p>Proof:</p> <p>After every multiple of 4 numbers has been assigned, A and B both contain the same number of items, and the sum of the items in each group are the same because</p> <pre><code>(n) + (n - 3) == (n - 1) + (n - 2) </code></pre> <p>In the last iteration we are at Step 1 above and we have either 0, 1 <a href="http://en.wikipedia.org/wiki/Knapsack_problem" rel="nofollow noreferrer">1</a>, 2 [1,2], or 3 [1,2,3] numbers remaining.</p> <p>In case 0, we are done and the groups are equal in count and weight.</p> <p>In case 1, we assign the number 1 to group A. Group A has one more item and one more weight. This is as fair as we can get in this situation.</p> <p>In case 2, we assign the number 2 to group A and the number 1 to group B. Now the groups have the same number of items and group A has one extra weight. Again, this is as fair as we can get.</p> <p>In case 3, assign the number 3 to group A, and assign numbers 2 and 1 to group B. Now the groups have the same weight (3 == 2 + 1) and group B has one extra item.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload