Question

Could anyone give a good detailed explanation of the following classic DPs? a) coin change, b) knapsack

Answer 1

Might as well explain them, for coin change, there is an input of coins, (eg. 5 1cent 3 5cent 4 10cent 1 20cent). And an input of desire amount (eg. 8cents.) Output should be least number of coins necessary.

Answer 2

For knapsack, you have a knapsack of fixed carrying capacity, and their are items on the ground. Each item has a volume and a value. Figure out the maximum value obtainable given the capacity of the bag and a list of items.

Answer 3

These are both supposed to be classic DP problems, trying to understand the solutions. Help please?

Answer 4

DPs are just divide and conquer problem where u break the problem into simpler subproblems. The subproblems will repeat several times so it waste time, the solution its to store each recursion call in some structure. I think its better to do first the problem in a divide and conquer form and then convert that to a DP.

well for the knapsack u got some objects wit v_i values and some w_i weight, and u cant put more than W in weight. There are two versions, the unbounded one where u can put the same objects all the time u want. The first one its quite easy, u just have a wieght and u dont care wich object u have added, so an array its all u need.


m[0]=0
m[w]=max(m[w-1], max (v_i + m[w - w_i]))
w_i <= w

The solution its m[W]

this means with weight 0 ur value its 0. With weight w, the first part in that max its just in any case that u cant add anything, and the other part its the its just the best of adding some of the objects to value u have the optimal. The divide and conquer its quite simple (u go in a top-down way here):

int getVal(int weight){
if( weight its one of the w_i) return v_i;
if( weight is less than any of the w_i) return 0;
for(i that is an object){
int maxi = 0
maxi = max(maxi, getVal(w - w_i) + v_i)
}
return i;
}

Now with the 0-1 its a little more complicated, u will have to take into account how many objects u have used, so u will need a matrix. U will have m[i,w] where i its that u have used up to i of the objects(yea u have then ordered and that never change) and w its the wieght of it.So now u have:

When u have 0 objects ur value its 0 in any weight:
m[0,w] = 0
When u have no weight ur value its 0
m[i,0] = 0
U cant any item that pass W
m[i,w] = m[i-1,w] if w_i > W
And finally u have
m[i,w] = max(m[i-1,w], max[i-1, w - w_i] + v_i) where w_i <W

The last one its u dont add anything or the best object u can add to an already optimal value.

The solution its m[n,W] were n its the number of objects.

i took all this from http://en.wikipedia.org/wiki/Knapsack_problem

Now the change problem

its quite similar to the last Knapsack, but u can add an item several times, so u just need to modify it a little bit. U have n coins with d_i value and want to give a k change.

m[i,c] its the number of coins up to i, with c cents of change. U will have

m[0,c] = c
m[i,0] = 0

And now u that u can add a limited number of coint u have this:

m[i,c] = k+1
for(j = 1; j <= number of times u have coin i: j++){
m[i,c] = min(m[i,c], m[i, c - j*d_i])
}
m[i,c] = min(m[i,c], m[i-1,c])

First u get the minum by adding as many i coins u can, and then check if its better to not add it.

The solution its m[n,k].

For this one i used this http://ace.cs.ohiou.edu/~razvan/courses/cs404/lecture19.pdf with some modifications of me. I think they are ok, but an error its allways posible, hope u get the idea. And yea my english sucks, spanish its the lenguage i know.

Answer 5

ok i have some mistakes in the one of the change in the for its
m[i,c] = min(m[i,c], 1+m[i, c - j*d_i]), in the second link u can check it working better

Answer 6

lol forget the first sentece, just change that in the change coint problem