# bounded knapsack problem (BKP)

### Description

Assume that you have`n`yuan. There are many kinds of rice in the supermarket. Each kind of rice is bagged and must be purchased in the whole bag. Given the`weight`,`price`and`quantity`of each type of rice, find`the maximum weight`of rice that you can purchase.

### Example

``````Given:
n = 8
prices = [2,4]
weight = [100,100]
amounts = [4,2]

Return:400
``````

800.Backpack IX

## Analysis & Solution

### 多重背包问题

#### Approach - DP

• 状态`dp[i][j]` 表示从前`i`种物品中选取若干种，这若干种物品在总价值不大于`j`的前提下，所能获得的最大总重量
• 转移方程：分两种情况。如果第`i`种物品不取，那么`dp[x][j] = dp[y][j]`。如果第`i`种物品取了，那就可能有`amount[i-1]`种取法，那么每一种取法都要考虑，第`k`种取法，就会增加`k * price[i - 1]`价值（花费）和`k * weight[i - 1]` 重量。

State Transfer Function
`dp[i][j] = max(dp[i - 1][j - k * price[i - 1]] + k * weight[i - 1]), k: 0 ~ amounts if j - k * price[i - 1]`

• 初始条件

• `dp[0][j] = 0`
• `dp[i][0] = 0`
• 答案`dp[m][n]`

2D - DP

``````public class Solution {
/**
* @param n: the money of you
* @param prices: the price of rice[i]
* @param weight: the weight of rice[i]
* @param amounts: the amount of rice[i]
* @return: the maximum weight
*/
public int backPackVII(int n, int[] prices, int[] weight, int[] amounts) {
int m = prices.length;
// dp[i][j]: first ith prices, using j money, maximum weight
int[][] dp = new int[m + 1][n + 1];
dp[0][0] = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = dp[i - 1][j];
for (int k = 1; k <= amounts[i - 1]; k++) {
if (j >= k * prices[i - 1]) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * prices[i - 1]] + k * weight[i - 1]);
}
}
}
}
return dp[m][n];
}
}
``````

1D DP Optimization

``````    public int backPackVII(int n, int[] prices, int[] weight, int[] amounts) {
int all = prices.length;
int[] f = new int [n + 1];
for (int i = 1; i <= all; i++) {
for (int k = 1; k <= amounts[i - 1]; k++) {
for (int j = n; j >= prices[i - 1]; j--) {
f[j] = Math.max(f[j], f[j - prices[i - 1]] + weight[i - 1]);
}
}
}
return f[n];
}
``````