【动态规划/背包问题】多重背包の二进制优化 ｜Python 主题月

本文正在参加「Python主题月」，详情查看 [活动链接](https://juejin.cn/post/6979532761954533390/)
复制代码

输入: N = 2, C = 5, v = [1,2], w = [1,2], s = [2,1]   
输出: 4
解释: 选两件物品 1，再选一件物品 2，可使价值最大。
复制代码

class Solution {
    public int maxValue(int N, int C, int[] s, int[] v, int[] w) {
        // 扁平化
        List<Integer> worth = new ArrayList<>();
        List<Integer> volume = new ArrayList<>();
        // 我们希望每件物品都进行扁平化，所以首先遍历所有的物品
        for (int i = 0; i < N; i++) {
            // 获取每件物品的出现次数
            int val = s[i];
            // 进行扁平化：如果一件物品规定的使用次数为 7 次，我们将其扁平化为三件物品：1*重量&1*价值、2*重量&2*价值、4*重量&4*价值
            // 三件物品都不选对应了我们使用该物品 0 次的情况、只选择第一件扁平物品对应使用该物品 1 次的情况、只选择第二件扁平物品对应使用该物品 2 次的情况，只选择第一件和第二件扁平物品对应了使用该物品 3 次的情况 ... 
            for (int k = 1; k <= val; k *= 2) { 
                val -= k;
                worth.add(w[i] * k);
                volume.add(v[i] * k);
            }
            if (val > 0) {
                worth.add(w[i] * val);
                volume.add(v[i] * val);
            }
        }
        // 0-1 背包问题解决方案
        int[] dp = new int[C + 1];
        for (int i = 0; i < worth.size(); i++) {
            for (int j = C; j >= volume.get(i); j--) {
                dp[j] = Math.max(dp[j], dp[j - volume.get(i)] + worth.get(i));
            }
        }
        return dp[C];
    }
}
复制代码

class Solution:
    def maxValue(self, N, C, s, v, w):
        # 扁平化
        worth = []
        volume = []
        # 我们希望每件物品都进行扁平化，所以首先遍历所有的物品
        for i in range(N):
            # 获取每件物品的出现次数
            val = s[i]
            # 进行扁平化：如果一件物品规定的使用次数为 7 次，我们将其扁平化为三件物品：1*重量&1*价值、2*重量&2*价值、4*重量&4*价值
            # 三件物品都不选对应了我们使用该物品0次的情况、只选择第一件扁平物品对应使用该物品1次的情况、只选择第二件扁平物品对应使用该物品2次的情况，只选择第一件和第二件扁平物品对应了使用该物品3次的情况...
            k = 1
            while k <= val:
                val -= k
                worth.append(w[i] * k)
                volume.append(v[i] * k)
                k *= 2
            if val > 0:
                worth.append(w[i] * val)
                volume.append(v[i] * val)
        # 0-1 背包问题解决方案
        dp = [0] * (C + 1)
        for i in range(len(worth)):
            for j in range(C, volume[i] - 1, -1):
                dp[j] = max(dp[j], dp[j-volume[i]] + worth[i])
        return dp[C]
复制代码