Dynamic programming

Question

Never had to deal with DP.
We have N stones with weights W_1, ..., W_N. It is necessary to divide all the stones into 2 parts, so that the difference between them was minimal.

Since we have n = 6, and weight = 1,4,5,6,7,9, the 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 next delete[] a; system("PAUSE"); return 0; } 

Answer 1

The idea of ​​dynamic programming is to calculate the answer iteratively, at each step, using the answers already calculated in the previous steps. See how this can 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 ]; 

We construct a reachable set containing all possible sums that can be achieved in one 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 ] ); } 

Please note that DP works here: having already built all the possible amounts that can be achieved using the first i - 1 stones, we are trying to add the i stone to each of them to get the same all possible amounts for i stones. We also add weight if the i stone by itself after gaining to avoid getting the impossible weight a[ i ] + a[ i ] (since each stone can be used no more than once). After this step, we get all the possible weights formed with each stone used no more than once.

Obviously, if the weight of one part *it (one of the many elements), then the weight of the other part will be sum - *it , so their difference will be fabs( sum - 2 * (*it)) . Find the 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; 

Answer 2

1 - If you are encoding ACM, avoid dynamic allocation of / new . It is slower and is an exception due to segfaults. Try to statically highlight everything by looking at the borders from the problem statement.

2 - The problem you want to solve is the Backpack problem. If you want, you can find many resources and solutions for it on the Internet / Wikipedia.

3 - In the deal with DP, caching is used, you only need to calculate the values ​​of the recursive function once. In your case, you have 2 ^ n possible spplitings of stones, but provided that each stone has a maximum weight W, for a set of stones there is only n * W weight.

So, can we make a function F (w) that determines if there are many stones in a stone that contain up to w? If so, we can find an algorithm with only n * W iterations instead of 2 ^ n!

The answer is yes! But you probably need to place some order to make it work. Let G (w, n) be defined as follows:

 G(w, n) = (true, s) if there is some set s containing only from the first n stones that adds up to w (false, _) if there is no such set. 

Now we need to compute G (w, NROCKS) to find F (w)!

It is easy to find a recursive definition that computes G:

 G(0, 0) = (true, {}) G(W, 0) = (false, _) G(W, N) = G(W, N-1) //we don't use the N-th rock - //find solution with remaining rocks instead. OR G(W - w(N), N-1) //if we use the N-th rock, assumin its wheigh is given by w(N) //our problem reduces to seeing if it is possible to add up to // W - w(N) using only the remaining rocks 

Although you could just directly implement this function, it will still have exponential runtime (I won this, but think about an example of a traditional fibonacci function).

The DP trick accurately observes that there is a limited number of inputs that we will ever use for this function (from 0 to NROCKS * max (MAXWEIGHT) and N from 0 to NROCKS), so we can use NROCKS * MAXWEIGHT in the matrix NROCKS (or something similar) as a look-up table to avoid double-computing.