Dynamic programming [closed]

Question

Never had to deal with the DP.
We have N stones with weights W_1,...,W_N. Need divide all stones for 2 parts, that difference between them was minimal.

As we have n = 6, and weight = 1,4,5,6,7,9 then difference is 0.

#include <iostream>

using namespace std;

int main()
{
    int     n; // numbers of stones
    int*    a; // array of weights
    int diff=0;
    cin >> n;
    a = new int[n];
    for(int i=0;i<n;i++)
        cin >> a[i];

    // And I don't know what's next, mee too

    delete[] a;
    system("PAUSE");
    return 0;
}

Answer 1

The idea of Dynamic Programming is to calculate the answer iteratively, on each step using the answers already calculated on previous steps. Let's see how this might be implemented for your problem:

Let sum be the sum of all elements:

int sum = 0;
for( int i = 0; i < n; ++i )
   sum += a[ i ];

Let's construct a reachable set, which contains all possible sums that can be achieved in a single part:

std::set< int > reachable;
for( int i = 0; i < n; ++i )
{
   for( set< int >::iterator it = reachable.begin(); it != reachable.end(); ++it )
      reachable.insert( *it + a[ i ] );
   reachable.insert( a[ i ] );
}

Note how DP works here: having already constructed all possible sums which can be achieved using first i - 1 stones we try to add i-th stone to each of them to get the same all possible sums for i stones. Also we add the weight if i-th stone itself to the set after the loop to avoid getting an impossible weight a[ i ] + a[ i ] (because each stone can be used at most once). After this step we get all possible weights formed with each stone used at most once.

Obviously if the weight of one part is *it (one of the set elements) then the weight of other part will be sum - *it, so their difference will be fabs( sum - 2 * (*it)). Let's find that minimum:

diff = sum; // maximal difference, when all stones are in one part
for( set< int >::iterator it = reachable.begin(); it != reachable.end(); ++it )
   diff = min( diff, fabs( sum - 2 * (*it) ) );
std::cout << "The answer is " << diff << std::endl;