背包九讲之分组背包问题

2021-03-24

[toc]

说明:

本文所讲内容摘录自崔添翼:背包九讲,并对其中的数学内容和一些较为复杂的内容进行了删减,增加了基础的例题,只是面向初学者或者不需要深入理解背包及其衍生问题的读者,如果有能力并且有意愿加深理解,本文可能会对您形成误导,请移步崔添翼:背包九讲.

分组背包问题

题目

有 N 件物品和一个容量为 V 的背包。第 i 件物品的费用是 $C_i$，价值是 $W_i$。这些物品被划分为 K 组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

基本思路

这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。也就是说设 $F[k, v]$ 表示前 k 组物品花费费用 v 能取得的最大权值(收益)，则有：
$$
F[k, v] = max\left{F[k − 1, v], F[k − 1, v −C_i] +W_i \space|\space item \space i ∈ group\space k\right}
$$

注意哦❗k代表组,v代表物品的容量,这个group隐含了一层意思就是对于这个组内的每个元素都要遍历一遍的,这个公式代表的是一个三层循环,具体的转移方程还是看伪代码比较好理解一些.

上述问题的伪代码

int N, V;
// cv[i][j][0]是放第i件物品消耗的费用,cv[i][j][1]是放第i件物品的收益价值,其中i从1开始
// GN是每个组内的元素的数量
int[][][] cv = new int[N + 1][GN][2];
int dp[][] = new int[N + 1][V + 1];
dp[0][0] = 0;
for (int i = 1; i <= N; i++) {
    for (int j = 0; j <= V; j++) {
        for (int k = 0; k < cv[i].length; k++) {
            if(cv[i][k][0]<=j){
                dp[i][j] = Math.max(dp[i-1][j],Math.max(dp[i][j], dp[i - 1][j - cv[i][k][0]] + cv[i][k][1]));
            }else{
                dp[i][j] = Math.max(dp[i-1][j],dp[i][j]);
            }
            
        }
    }
}
return dp[N][V];

注意❗: 外层i枚举物品的数量,内层j枚举背包的容量，最内层k枚举组内的每个元素

注意❗❗❗: 转移方程为dp[i][j] = Math.max(dp[i-1][j],Math.max(dp[i][j], dp[i - 1][j - cv[i][k][0]] + cv[i][k][1]));(物品容量小于背包容量)和dp[i][j] = Math.max(dp[i-1][j],dp[i][j]);(物品容量大于背包容量)

一个简单有效的优化

略🚮🤐(太菜了,慢慢来)

相关题目练习

题目URL

有 N 组物品和一个容量是 V 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 $v_{ij}$，价值是 $w_{ij}$，其中 i 是组号，j 是组内编号。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

输入格式

第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。

接下来有 N 组数据：

每组数据第一行有一个整数 $S_i$，表示第 i 个物品组的物品数量；
每组数据接下来有 $S_i$ 行，每行有两个整数 $v_{ij},w_{ij}$，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值；

输出格式

输出一个整数，表示最大价值。

数据范围

$0<N,V≤1000<N,V≤100$
$0<S_i≤1000<S_i≤100$
$0<v_{ij},w_{ij}≤1000<v_{ij},w_{ij}≤100$

输入样例

输出样例：

题目解法

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 物品的组数量
        int N = sc.nextInt();
        // 背包的容量
        int V = sc.nextInt();
        // 每个物品的体积和价值
        int[][][] gvw = new int[N + 1][][];

        for (int i = 1; i <= N; i++) {
            // 第 i 个物品组的物品数量
            int Si = sc.nextInt();
            gvw[i] = new int[Si][2];
            for (int j = 0; j < Si; j++) {
                // 体积
                gvw[i][j][0] = sc.nextInt();
                // 价值
                gvw[i][j][1] = sc.nextInt();
            }

        }

        int dp[][] = new int[N + 1][V + 1];
        // 不要求完全装满背包,初始化全设置为0,因为java默认int数组为0所以象征性的初始化第一个
        dp[0][0] = 0;
        // 枚举第i件物品
        for (int i = 1; i <= N; i++) {
            // 枚举背包的容量j
            for (int j = 0; j <= V; j++) {
                // 枚举选择第i种物品的数量k
                for (int k = 0; k < gvw[i].length; k++) {
                    if (gvw[i][k][0] <= j) {
                        // 在组之间有选择或不选择当前组这两种情况,在组内也有两种情况,
                        // 分别是选择当前组内的当前元素和不选择当前组内的当前元素
                        
                        // 在组之间,不选择当前的组,问题转化成i-1个组容量为j的背包最多能装下物品的收益即:dp[i-1][j]
                        // 在组之间,选择当前的组,问题转化成第i个组内选择和不选择第k个物品的问题,描述如下:
                        
                        // 在组内不选择第k个物品时,目前的最大收益是dp[i][j](可能选择了某个物品,也可能没有选择某个物品),
                        // 在组内选择第k个物品时,收益是通过没选择当前组的收益转移而来的,
                        // 选择第k个物品消耗的容量是gcw[i][k][0],问题转化成i-1个组,
                        // 容量为j-gcw[i][k][0]的背包最多能装下的物品的最大收益,是dp[i-1][j-gvw[i][k][0]]
                        dp[i][j] = Math.max(dp[i - 1][j], Math.max(dp[i][j], dp[i - 1][j - gvw[i][k][0]] + gvw[i][k][1]));
                    } else {
                        // 这里需要注意的是如果背包的容量小于当前组内物品的体积,
                        // 那么需要比较不选当前组的任何物品时的收益与
                        // 当前组内的收益作比较(当前组内可能已经选择了某些,也可能没有选择,没有选择时值是dp[i - 1][j])
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j]);
                    }
                }
            }
        }
        // 返回N件物品,背包容量为V的装入的最大价值
        System.out.println(dp[N][V]);
    }
}

参考文献

崔添翼:背包九讲