Dynamic Programming w/ 1D array USACO Training: Subset Sums

Question

While working through the USACO Training problems, I found out about Dynamic Programming. The first training problem that deals with this concept is a problem called Subset Sums.

The Problem Statement Follows:

---

For many sets of consecutive integers from 1 through N (1 <= N <= 39), one can partition the set into two sets whose sums are identical. For example, if N=3, one can partition the set {1, 2, 3} in one way so that the sums of both subsets are identical:

{3} and {1,2}

This counts as a single partitioning (i.e., reversing the order counts as the same partitioning and thus does not increase the count of partitions). If N=7, there are four ways to partition the set {1, 2, 3, ... 7} so that each partition has the same sum:

{1,6,7} and {2,3,4,5}

{2,5,7} and {1,3,4,6}

{3,4,7} and {1,2,5,6}

{1,2,4,7} and {3,5,6}

Given N, your program should print the number of ways a set containing the integers from 1 through N can be partitioned into two sets whose sums are identical. Print 0 if there are no such ways. Your program must calculate the answer, not look it up from a table.

INPUT FORMAT The input file contains a single line with a single integer representing N, as above.

SAMPLE INPUT (file subset.in) 7

OUTPUT FORMAT The output file contains a single line with a single integer that tells how many same-sum partitions can be made from the set {1, 2, ..., N}. The output file should contain 0 if there are no ways to make a same-sum partition. SAMPLE OUTPUT (file subset.out) 4

---

After much reading, I found an algorithm that was explained to be a variation of the 0/1 knapsack problem. I implemented it in my code, and I solved the problem. However, I have no idea how my code works or what is going on.

*Main Question: I was wondering if someone could explain to me how the knapsack algorithm works, and how my program could possibly be implementing this in my code?

My code:

 #include <iostream>
 #include <fstream>
 using namespace std;
 int main()
 {
      ifstream fin("subset.in");
      ofstream fout("subset.out");
      long long num=0, ways[800]={0};
      ways[0]=1;
      cin >> num;

      if(((num*(num+1))/2)%2 == 1)
      {
           fout << "0" << endl;
           return 0;
      }
      //THIS IS THE BLOCK OF CODE THAT IS SUPPOSED TO BE DERIVED FROM THE 
      //   O/1 KNAPSACK PROBLEM
      for (int i = 1; i <= num; i++) 
      {
           for (int j = (num*(num+1))/2 - i; j >= 0; --j) 
           {
                ways[j + i] += ways[j];
           }
      }
      fout << ways[(num*(num+1))/2/2]/2 << endl;
      return 0;
 }

*note: Just to emphasize, this code does work, I just would like an explanation why it works. Thanks :)

Answer 1

I wonder why numerous sources could not help you.

Trying one more time with my ugly English:

ways[0]=1;

there is a single way to make empty sum

num*(num+1))/2

this is MaxSum - sum of all numbers in range 1..num (sum of arithmetic progression)

if(((num*(num+1))/2)%2 == 1)

there is no chance to divide odd value into two equal parts

for (int i = 1; i <= num; i++)

for every number in range

for (int j = (num*(num+1))/2 - i; j >= 0; --j) ways[j + i] += ways[j];

sum j + i might be built using sum j and item with value i.

For example, consider that you want make sum 15.
At the first step of outer cycle you are using number 1, and there is ways[14] variants to make this sum.
At the second step of outer cycle you are using number 2, and there is ways[13] new variants to make this sum, you have to add these new variants.
At the third step of outer cycle you are using number 3, and there is ways[12] new variants to make this sum, you have to add these new variants.

ways[(num*(num+1))/2/2]/2

output number of ways to make MaxSum/2, and divide by two to exclude symmetric variants ([1,4]+[2,3]/[2,3]+[1,4])

Question for self-thinking: why inner cycle goes in reverse direction?