Problem 17.7 Answer

#1

I’m a bit confused on this. Suppose the items had the values: 510, 290 and 200. The sum is 1000. The most fair divide is 510 in one and 290+200 in the other. The answer should be 20 for the minimal difference. However the answer in the book is not this. The answer in the book is (1000-290)-290 = 420. Please help.

0 Likes
#2

i’m not sure how you came up with 290 in (1000 - 290) - 290 = 420.
the last line of book’s solution will actually be (1000 - 490) - 490 = 20;

the solution is using a simple dp table…

Set<Integer> isOk = new HashSet<>();
isOk.add(0);
for (int item : A) {
  for (int v = sum / 2; v >= item; --v) {
    if (isOk.contains(v - item)) {
      isOk.add(v);
    }
  }
}

w/ your example, this code will compute,

isOk[0] = true; // given
isOk[200] = true; // isOk[200 - 200] == isOk[0] == true;
isOk[290] = true; // isOk[290 - 290] == isOk[0] == true;
isOk[490] = true; // isOk[490 - 290] == isOk[200] == true; or could do 490 - 200 too.

… and that’s the end of the dp table filling.

so

for (int i = sum / 2; i > 0; --i) {
  if (isOk.contains(i)) {
    return (sum - i) - i;
  }
}

starting from i = 500,

it’ll stop at 490, and return (1000 - 490) - 490 = 20

0 Likes
#3

Thanks for the response. Did the item with value of 510 get added as 490?

0 Likes
#4

no; 510 isn’t added at all to the dp table because its value is bigger than sum / 2 (= 500). 490 is added to the table due to 290 and 200.

0 Likes
#5

Thanks, I had a typo in my code. I was adding item instead of v.

0 Likes