> For the complete documentation index, see [llms.txt](https://aaronice.gitbook.io/lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aaronice.gitbook.io/lintcode/knapsack_problems/backpack-vii.md).

# Backpack VII

## Backpack VII (多重背包问题）

## 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
```

#### Related Problems

[800.Backpack IX](https://www.lintcode.com/problem/backpack-ix)

### Analysis & Solution

#### 多重背包问题

这个问题与 0-1 背包的区别在于，0-1 背包中每种物品有且只有一个，而多重背包中一种物品有nums\[i] 个。

**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**

```java
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**

这题也可以用 Backpack II 中的一维数组倒序解法。只不过就在倒序遍历价格范围之前，遍历`amounts[i - 1]`次第`i`中物品有的数量。时间复杂度是O(all \* n \* sum(amounts\[i - 1] )), 空间复杂度是dp\[n]

```java
    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];
    }
```