Backpack VII

Backpack VII (多重背包问题）

bounded knapsack problem (BKP)

Description

Assume that you havenyuan. There are many kinds of rice in the supermarket. Each kind of rice is bagged and must be purchased in the whole bag. Given theweight,priceandquantityof each type of rice, findthe maximum weightof 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

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

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]

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