Code for dividing gifts equally

I recently came across this problem:


It is Lavanya's birthday and several families have been invited for
the birthday party. As is customary, all of them have brought gifts
for Lavanya as well as her brother Nikhil. Since their friends are all
of the erudite kind, everyone has brought a pair of books.
Unfortunately, the gift givers did not clearly indicate which book in
the pair is for Lavanya and which one is for Nikhil. Now it is up to
their father to divide up these books between them.


He has decided that from each of these pairs, one book will go to
Lavanya and one to Nikhil. Moreover, since Nikhil is quite a keen
observer of the value of gifts, the books have to be divided in such a
manner that the total value of the books for Lavanya is as close as
possible to total value of the books for Nikhil. Since Lavanya and
Nikhil are kids, no book that has been gifted will have a value higher
than 300 Rupees.


Suppose there are 4 pairs of books whose cost in Rupees are:


(3,5), (7,11), (8,8), (2,9)


By giving the books worth 3,7,8 and 2 to Lavanya and the rest to
Nikhil, the net difference in value would be 5+11+8+9-3-7-8-2 = 13.
However, by giving books worth 3,7,8 and 9 to Lavanya and the rest to
Nikhil, their father can ensure that the difference in values is just
1. You can verify that you cannot do better than this.


You task is to help their father decide how to divide the books.

My approach is take the difference of of every pair and arrange them in descending order, where one by one they are subtracted if the previous result was positive or added if previous result was negative. This greedy approach works for most of the test cases but gets stuck at some.

```
#include
#include
#include

int main (int argc, char const* argv[])
{
int n;
std::cin >> n;
int difference[n];
for(int i=0;i>a >>b;
difference[i] = std::abs(a-b);
}
std::sort(difference , difference+n,std::gr

Greedy solution not correct

First, we can transform the problem as OP did by taking the difference of the book values in each pair, and then trying to split these new values in to two equal halves. In the example of (3,5), (7,11), (8,8), (2,9), this transforms into trying to split 2 4 0 7 into equal halves, which is achieved as closely as possible with the solution [0,2,4][7].

The greedy solution attempts to place the largest unused value on the smallest pile. In the example above, the sorted values are 7 4 2 0, and the values are placed in the following way:

Pile 1 Pile 2
------ ------
7
7 4
7 4,2
7 4,2,0


leading to the correct answer.

However, consider the case of 5 5 4 3 3. In this case, the greedy method would place the values as follows:

Pile 1 Pile 2
------ ------
5
5 5
5,4 5
5,4 5,3
5,4 5,3,3


Ending with piles of size 9 and 11, with a difference of 2. However, the optimal solution would be piles [5,5][4,3,3] with a difference of 0.

Dynamic Programming

Instead of a greedy method, you can use a dynamic programming method to solve the problem. The algorithm will be as follows:

• Transform the initial input by taking the absolute value of the differences between each pair of books. This is the new list of values we will use.

• Sum the list of values. Call this sum total. We are now trying to find a subset of the values that will sum as closely to total/2 as possible (without going over). You can convince yourself that this subset will provide us with the best answer to the problem.

• Create an array of booleans of size (total/2) + 1 and initialize to false, except for element arr[0] which you initialize to true. Each element of this array contains whether it is possible to reach a sum of that index. For example, if in the end, arr[15] is true, then it is possible to create a subset that sums to 15.

• For each element in the list of values, you traverse the array, and whenever you find arr[j] to be true, you can set arr[j+val] to be true. Note: this traversal needs to start at arr[max-val] and search towards arr[0]. If you traverse in the forwards direction, the act of setting arr[j+val] to true will cause that array element to trigger later in the loop when it shouldn't. For example, if val were 1, the forwards loop would mistakenly set every element in the array to true.

• Once step 4 is finished, your array holds all the possible subsums. Find the largest possible subsum, and that will be the value of one pile. Call that value largestSum. The other pile will have value total - largestSum. The difference will be total - 2*largestSum, which is the answer to the question.

This approach will have complexity \$O(n * m)\$, where \$n\$ is the number of book pairs and \$m\$ is the total of all the differences. In the problem description, there are max 150 books with max value 300, so the maximum value for \$m\$ is 45000.

Compare this to the recursive solution which tries to place each value in each pile, which has complexity \$O(2^n)\$.

Sample implementation using dynamic programming

I took your program and adjusted it to use the dynamic programming approach described above. Here is the result:

#include 
#include 
#include 

int main (int argc, char const* argv[])
{
    int n;
    std::cin >> n;
    int difference[n];
    int total = 0;
    for(int i=0;i>a >>b;
        difference[i] = std::abs(a-b);
        total += difference[i];
    }

    // Find each reachable sum up to total/2.
    int  max = total/2;
    bool arr[max+1] = { true };
    for (int i = 0; i = 0; j--) {
            if (arr[j])
                arr[j+val] = true;
        }
    }

    // Find the max reachable sum.  For that sum, print the difference between
    // one child's sum (i) and the other's (total - i).  Since i is always
    // less than or equal to (total - i), the difference will be total - i - i.
    for (int i = max; i >= 0; i--) {
        if (arr[i]) {
            std::cout << total - i - i << std::endl;
            break;
        }
    }
    return 0;
}

StackExchange Code Review Q#143589, answer score: 2