Givenn_kind of items with size Aiand value Vi(each item has an infinite number available) and a backpack with size_m. What's the maximum value can you put into the backpack?
You cannot divide item into small pieces and the total size of items you choose should smaller or equal to m.
Example
Given 4 items with size[2, 3, 5, 7]and value[1, 5, 2, 4], and a backpack with size10. The maximum value is15.
可以无限使用物品, 就失去了last i, last unique item的意义: 因为可以重复使用. 所以可以转换一个角度:
i. 用 i种 物品, 拼出j大小, 并且满足题目条件(max value). 这里因为item i可以无限次使用, 所以考虑使用了多少次K.
ii. k虽然可以无限, 但是也被 k * A[i]所限制: 最大不能超过背包大小.
dp[i][j]: 前i种物品, fill weight j 的背包, 最大价值是多少.
dp[i][j] = max {dp[i - 1][j - k*A[i-1]] + k*V[i-1]}, k >= 0, k <= j / A[i-1]
Time: O(nmk)
如果k = 0 或者 1, 其实就是 Backpack II: 0-1背包，拿或者不拿
2D - DP 代码实现：
/*
Thoughts:
dp[i][w]: first i types of items to fill weight w, find the max value.
1st loop: which type of item to pick from A
2nd loop: weight from 0 ~ m
3rd loop: # times when A[i] is used.
Goal: dp[n][m]
Condition1: didn't pick A[i - 1], dp[i][j] = dp[i - 1][j];
Condition2: pickced A[i - 1], dp[i][j] = dp[i - 1][j - k * A[i - 1]] + k * V[i - 1];
O(nmk)
*/
public class Solution {
public int backPackIII(int[] A, int[] V, int m) {
if (A == null || A.length == 0 || V == null || V.length == 0 || m <= 0) {
return 0;
}
int n = A.length;
int[][] dp = new int[n + 1][m + 1];
dp[0][0] = 0; // 0 items to fill 0 weight, value = 0
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j] = dp[i - 1][j];
for (int k = 1; k * A[i - 1] <= j; k++) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * A[i - 1]] + k * V[i - 1]);
}
}
}
return dp[n][m];
}
}
Minor Modified
public class Solution {
public int backPackIII(int[] A, int[] V, int m) {
if (A == null || A.length == 0 || V == null || V.length == 0 || m <= 0) {
return 0;
}
int n = A.length;
int[][] dp = new int[n + 1][m + 1];
dp[0][0] = 0; // 0 items to fill 0 weight, value = 0
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
for (int k = 0; k * A[i - 1] <= j; k++) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * A[i - 1]] + k * V[i - 1]);
}
}
}
return dp[n][m];
}
}
