背包问题（六）--分组背包

参考资料
背包九讲
https://www.acwing.com/activity/content/11/

分组背包模型

背包容量为V，有N组物品，每组物品只能选一件，第i组内的第j件物品容量cij，价值wij，求背包能放的最大价值

思路
f(i,v)表示从前i组物品选，体积小于等于v的最大价值
f(i,v) = max(f(i-1,v) , f(i-1,v-cij)+wij)
civ表示第i组的第j个物品的体积，wij表示第i组的第j个物品的价值

代码实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int V = sc.nextInt();
        int[][] v = new int[110][110];
        int[][] w = new int[110][110];
        int[] s = new int[110];

        for (int i = 1; i <= N; i++) {
            s[i] = sc.nextInt();
            for (int j = 0; j < s[i]; j++) {
                v[i][j] = sc.nextInt();
                w[i][j] = sc.nextInt();
            }
        }

        // 分组背包
        int[][] dp = new int[N + 1][V + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= V; j++) {
                for (int k = 0; k < s[i]; k++) {
                    if(j<v[i][k]){
                        // 注意，这里不能直接写dp[i][j] = dp[i-1][[j]。我们要选的是当前组的最大值，而
                        // 不是选和不选当前商品的最大值
                        dp[i][j] = Math.max(dp[i][j],dp[i-1][j]);
                    } else {
                        // 此处同理，要选择当前组的最大值
                        dp[i][j] = Math.max(dp[i][j], 
                                        Math.max(dp[i-1][j],dp[i - 1][j - v[i][k]] + w[i][k]));
                    }
                }
            }
        }
        System.out.println(dp[N][V]);
    }
}

空间复杂度优化
滚动数组，二维数组降维到一维数组

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int V = sc.nextInt();
        int[][] v = new int[N+1][110];
        int[][] w = new int[N+1][110];
        int[] s = new int[N+1];

        for (int i = 1; i <= N; i++) {
            s[i] = sc.nextInt();
            for (int j = 0; j < s[i]; j++) {
                v[i][j] = sc.nextInt();
                w[i][j] = sc.nextInt();
            }
        }

        // 分组背包
        
        int[] dp = new int[V + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = V; j >= 0; j--) {
                for (int k = 0; k < s[i]; k++) {
                    if (j >= v[i][k]) {
                        dp[j] = Math.max(dp[j], dp[j - v[i][k]] + w[i][k]);
                    }
                }
            }
        }
        System.out.println(dp[V]);
    }
}