Code for dividing gifts equally

Question

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 <iostream>
#include <algorithm>
#include <cmath>

int main (int argc, char const* argv[])
{
    int n;
    std::cin >> n;
    int difference[n];
    for(int i=0;i<n;i++){
        int a,b;
        std::cin>>a >>b;
        difference[i] = std::abs(a-b);
    }
    std::sort(difference , difference+n,std::greater<int>());
    int diff = difference[0];
    for(int i=1;i<n;i++){
        if(diff > 0){
            diff = diff - difference[i];
        }else{
            diff = diff + difference[i];
        }
        std::cout << diff << std::endl;
    }
    std::cout << std::abs(diff) << std::endl;
    return 0;
} 

I have tried to implement recursion but it gets too complicated for me and often takes a lot more time for bigger test cases. Does anyone have any better approach for it?

Here are some testcases:

TestCase 1: Input: 5 271 6 293 148 194 104 4 207 148 267

Output: 2

TestCase 2: Input: 30 130 83 207 104 115 33 149 20 51 128 78 256 246 99 42 215 187 276 239 263 105 122 294 143 14 241 146 175 175 114 9 56 248 267 212 62 299 60 82 49 187 159 56 184 9 150 99 195 177 89 157 282 210 203 176 275 143 73 202 69

Output: 1

TestCase 3: Input: 50 185 294 180 119 96 18 82 75 26 25 120 55 40 230 31 105 112 140 22 227 154 29 187 107 156 182 181 57 122 39 90 59 84 269 177 180 287 258 6 64 34 126 171 74 107 201 230 218 93 4 197 246 32 135 104 239 16 284 47 189 75 136 247 158 157 176 89 195 185 147 10 219 272 180 44 130 133 273 100 225 276 296 222 59 130 25 49 197 60 96 85 134 283 84 44 139 259 184 85 143

Output: 0

Apparently this are the only testcases causing trouble.

Answer 1

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:

1. 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.
2. 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.
3. 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.
4. 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.
5. 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 <iostream>
#include <algorithm>
#include <cmath>

int main (int argc, char const* argv[])
{
    int n;
    std::cin >> n;
    int difference[n];
    int total = 0;
    for(int i=0;i<n;i++){
        int a,b;
        std::cin>>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 < n; i++) {
        int val = difference[i];
        for (int j = max - val; j >= 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;
}