背包问题java分组背包

分组背包问题是指将物品分为若干组，每组中的物品互相冲突，最多只能选择一件物品，求在总体积不超过背包容量的情况下，能获得的最大价值。Java实现分组背包问题的代码如下：

public static int groupKnapsack(int[] weight, int[] value, int[] group, int n, int m) {
    int[][] dp = new int[n + 1][m + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= weight[i]; j--) {
            for (int k = 1; k <= i; k++) {
                if (group[k] == group[i]) {
                    dp[k][j] = Math.max(dp[k][j], dp[k - 1][j - weight[i]] + value[i]);
                }
            }
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        res = Math.max(res, dp[i][m]);
    }
    return res;
}

其中，weight数组表示每个物品的重量，value数组表示每个物品的价值，group数组表示每个物品所属的组别，n表示物品的数量，m表示背包的容量。