Question description:
You have a container with volume of V which is used for stones picking up. There are i kinds of stones with only one for each kind, and each have a value of m[i] and volume of v[i], where i is in the range of (0, n]. What is the maximum value can you achieve with your container?
Notes:
This is a 01 knapsack problem. The key logic is: for each stone, we can either choose it or do not choose it. Or yes or no in short.
State transfer equation 1:
dp[i][v] = max(dp[i-1][v], dp[i-1][v- v[i]] + m[i]), v>= vi
dp[i][v] represents the maximum value using the first i kinds of stones with volume of v and for each kind of stones, we can pick up at most 1 time (since there is only 1 for each kind).
Code 1:
int 01kp_2D(vector<int> &v, vector<int> &m, int V) {
int len = v.size();
vector<vector<int>> dp(len+1, vector<int>(V+1, 0));
for(int i=1; i<=len; ++i) {
for(int j=v[i-1]; j<=V; ++j) {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i-1]] + m[i-1]);
}
}
return dp[len][V];
}
This code can be re-written into one dimensional array:
(why can we do this? If confused, print out the above 2D matrix, and track how dp[i][j] evolves from layer to layer. Pay attention to the relative positions in i and j.)
Code 2:
int 01kp_1D(vector<int> &v, vector<int> &m, int V) {
int len = v.size();
vector<int> dp(V+1, 0);
for(int i=1; i<=len; ++i) {
for(int j=V; j>=v[i-1]; --j) {
dp[j] = max(dp[j], dp[j-v[i-1]] + m[i-1]);
}
}
return dp[V];
}
2: Complete Knapsack Problems
Question description:
You have a container with volume of V which is used for stones picking up. There are i kinds of stones, and each have a value of m[i] and volume of v[i], where i is in the range of (0, n]. For each kind of stones, there are infinite number of stones. What is the maximum value can you achieve with your container?
Notes:
This is a complete knapsack problem. The key logic is: for each stone, there are infinite number of them. But actually we have a container with a finite size, V. Thus, for each kind of the stones, the effective number is [V/v[i]]. Now the problem becomes a Multiple Knapsack Problem, which will be covered in the next section. If we treat each stone in the same kind as that in the 01cp, then it is converted to an 01cp.
State transfer equation 2:
dp[i][v] = max(dp[i-1][v- k*v[i]] + k*m[i]), where v>=vi, 0<= k <= [V/v[i]]
dp[i][v] represents the maximum value using the first i kinds of stones with volume of v and for each kind of stones, we can pick up at most [V/v[i]] times.
Code 3:
int ckp_2D(vector<int> &v, vector<int> &m, int V) {
int len = v.size();
vector<vector<int>> dp(len+1, vector<int>(V+1, 0));
for(int i=1; i<=len; ++i) {
for(int k=0; k<=V/m[i-1]; ++k) {
for(int j=k*v[i-1]; j<=V; ++j) {
dp[i][j] = max(dp[i][j], dp[i-1][j-k*v[i-1]] + k*m[i-1]);
}
}
}
return dp[len][V];
}
Similar to that in 01 Knapsack Problem, we can reduce the space complexity from 2D to 1D. But the time complexity is still O(Len*V*K).
Can we do better?
Let us focus on the volume v, and dp[v] represents the maximum value using a container with volume of v. And for each kind of stones, we can pick up them as many as possible until the container is full.
State transfer equation 3:
dp[v] = max(dp[v- v[i]] + m[i]), v>= vi
It seems too simple to be true.
Let us look at the meaning of the each term. If we know dp[v-v[i]], or with a container with all possible smaller volumes, then dp[v] should be the maximum of all the possible combinations, as illustrated in the above equation. There is no limitation of number of stones for picking up, as long as it can fit in the container. So we can try all the kinds of stones at each layer of volume. Thus, the process of calculation dp[v] should start with smaller v's, or with a bottom-up protocol. This is the key difference between the Complete and the 01 Knapsack Problem.
Code 4:
int ckp_1D(vector<int> &v, vector<int> &m, int V) {
int len = v.size();
vector<int> dp(V+1, 0);
for(int j=1; j<=V; ++j) {//must from smaller v to bigger!
for(int i=1; i<=len; ++i) {
if(j>=v[i-1]) dp[j] = max(dp[j], dp[j-v[i-1]] + m[i-1]);
}
}
return dp[V];
}
The above two for loops can be switched,
Code 5:
int ckp_1D(vector<int> &v, vector<int> &m, int V) {
int len = v.size();
vector<int> dp(V+1, 0);
for(int i=1; i<=len; ++i) {
for(int j=1; j<=V; ++j) {//must from smaller v to bigger!
if(j>=v[i-1]) dp[j] = max(dp[j], dp[j-v[i-1]] + m[i-1]);
}
}
return dp[V];
}
Now let us look at a different way to derive the above ckp result. Let dp[i][v] represent the maximum value using the first i kinds of stones with volume of v and for each kind of stones, we can pick up as many times as possible, then
State transfer equation 4:
dp[i][v] = max(dp[i-1][v], dp[i][v- v[i]] + m[i]), v>= vi
The only difference between the above equation and that for the 01kp is the second term on the right side of the above equation: here we adopt dp[i][v-v[i]] and in 01kp we use dp[i-1][v-v[i]]. The former means we can use the ith stone to fill v-v[i], now we can use this stone again. The latter means we can only use this stone once. So the former is for the Complete Knapsack Problem, and the latter is for the 01 Knapsack Problem.
Code 6,
int ckp_2D(vector<int> &v, vector<int> &m, int V) {
int len = v.size();
vector<vector<int>> dp(len+1, vector<int>(V+1, 0));
for(int i=1; i<=len; ++i) {
for(int j=v[i-1]; j<=V; ++j) {
dp[i][j] = max(dp[i-1][j], dp[i][j-v[i-1]] + m[i-1]);
}
}
return dp[len][V];
}
It is easy to convert it to 1D, which then becomes the same as Code 5!
Code 7,
int ckp_1D(vector<int> &v, vector<int> &m, int V) {
int len = v.size();
vector<int> dp(V+1, 0);
for(int i=1; i<=len; ++i) {
for(int j=v[i-1]; j<=V; ++j) {//must from left to right.
dp[j] = max(dp[j], dp[j-v[i-1]] + m[i-1]);
}
}
return dp[V];
}
3: Multiple Knapsack Problems
The only difference now is that: for each kind of stone, we have known available total number n[i]. Similar to the Complete Knapsack Problem, we can convert it into 01kp.
State transfer equation 5:
dp[i][v] = max(dp[i-1][v- k*v[i]] + k*m[i]), where v>=vi, 0<= k <= n[i]
dp[i][v] represents the maximum value using the first i kinds of stones with volume of v and for each kind of stones, we can pick up at most n[i] times.
Code 8:
int mkp_2D(vector<int> &v, vector<int> &m, vector<int> &n, int V) {
int len = v.size();
vector<vector<int>> dp(len+1, vector<int>(V+1, 0));
for(int i=1; i<=len; ++i) {
for(int k=0; k<=n[i-1]; ++k) {
for(int j=k*v[i-1]; j<=V; ++j) {
dp[i][j] = max(dp[i][j], dp[i-1][j-k*v[i-1]] + k*m[i-1]);
}
}
}
return dp[len][V];
}
Can we do better? The answer again is yes! To be continued
No comments:
Post a Comment