【动态规划/背包问题】详解「完全背包」问题 & 三种背包问题之间的内在关系

输入: 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) {
        int[][] dp = new int[N][C + 1];
        
        // 先处理第一件物品
        for (int j = 0; j <= C; j++) {
            // 显然当只有一件物品的时候，在容量允许的情况下，能选多少件就选多少件（不超过限制数量）
            int maxK = Math.min(j / v[0], s[0]);
            dp[0][j] = maxK * w[0];
        }
        
        // 处理剩余物品
        for (int i = 1; i < N; i++) {
            for (int j = 0; j <= C; j++) {
                // 不考虑第 i 件物品的情况
                int n = dp[i- 1][j];
                // 考虑第 i 件物品的情况
                int y = 0;
                for (int k = 1; k <= s[i]; k++) {
                    if (j < k * v[i]) {
                        break;
                    }
                    y = Math.max(y, dp[i - 1][j - k * v[i]] + k * w[i]);
                }
                dp[i][j] = Math.max(n, y);
            }
        }
        
        return dp[N - 1][C];
    }
}

class Solution {
    public int maxValue(int N, int C, int[] s, int[] v, int[] w) {
        int[][] dp = new int[2][C + 1];
        
        // 先处理第一件物品
        for (int j = 0; j <= C; j++) {
            // 显然当只有一件物品的时候，在容量允许的情况下，能选多少件就选多少件（不超过限制数量）
            int maxK = Math.min(j / v[0], s[0]);
            dp[0][j] = maxK * w[0];
        }
        
        // 处理剩余物品
        for (int i = 1; i < N; i++) {
            for (int j = 0; j <= C; j++) {
                // 不考虑第 i 件物品的情况
                int n = dp[(i- 1)&1][j];
                // 考虑第 i 件物品的情况
                int y = 0;
                for (int k = 1; k <= s[i]; k++) {
                    if (j < k * v[i]) {
                        break;
                    }
                    y = Math.max(y, dp[(i - 1)&1][j - k * v[i]] + k * w[i]);
                }
                dp[i&1][j] = Math.max(n, y);
            }
        }
        
        return dp[(N - 1)&1][C];
    }
}

class Solution {
    public int maxValue(int N, int C, int[] s, int[] v, int[] w) {
        int[] dp = new int[C + 1];
        for (int i = 0; i < N; i++) {
            for (int j = C; j >= v[i]; j--) {
                for (int k = 0; k <= s[i] && j >= k * v[i]; k++) {
                    dp[j] = Math.max(dp[j], dp[j - k * v[i]] + k * w[i]);
                }
            }
        }
        return dp[C];
    }
}

class Solution {
    public int maxValue(int N, int C, int[] s, int[] v, int[] w) {
        // 将多件数量的同一物品进行「扁平化」展开，以 [v, w] 形式存储
        List<int[]> arr = new ArrayList<>(); 
        for (int i = 0; i < N; i++) {
            int cnt = s[i];
            while (cnt-- > 0) {
                arr.add(new int[]{v[i], w[i]});
            }
        }
        
        // 使用「01 背包」进行求解
        int[] dp = new int[C + 1];
        for (int i = 0; i < arr.size(); i++) {
            int vi = arr.get(i)[0], wi = arr.get(i)[1];
            for (int j = C; j >= vi; j--) {
                dp[j] = Math.max(dp[j], dp[j - vi] + wi);   
            }
        }
        return dp[C];
    }
}