Knapsack Problem
A thief robbing a safe finds it filled with N types of items of
varying size and value, but has only a small knapsack of capacity
M to use to carry the goods. The knapsack problem is to find the
combination of itmes which the thief should choose for his
knapsack in order to maximize the total value of all the items
he takes.
The Input
The first line in the input file will be two integer numbers
N and M, both 1<=N,M<=255. Each
next N lines will be a pair of integer v[i] and
s[i], i=1..N, giving the value and the size of
the i-th item.
The Output
The output will be N integer numbers. The i-th number
in the output will be the number of item i that the thief must
have in his knapsack to optimize the total value he takes.
Example
Input :
5 17
4 3
5 4
10 7
11 8
13 9
Output :
24
1 0 2 0 0
Solution :
The dynamic programming solution is to calculate the best
combination for all knapsack sizes up to M. We will use an
array Best to keep a record of the maximum value we
can get for the knapsacks. Say that we can get a maximum value
of x for a knapsack of size y. Now we have an
item whose value is a and whose size is b. It
is obvious that for a knapsack of size y+b we can get
a total value of x+a. If this new value is higher, we
will change the content of the array and update it.
In order to keep track of the actual content of the knapsack, we
will use another array Pred. Pred[i] is the
index of the last item added to a knapsack of size i,
thus we can calculate the predecessor of each knapsacks and
find out what items are actually inside each of them.
yogy-n@sby.mega.net.id
