背包九讲之01背包问题

2021-03-23

[toc]

说明:

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

01背包问题

题目

有 $N$ 件物品和一个容量为 $V$ 的背包。放入第 $i$ 件物品耗费的费用是 $C_i$得到的价值是 $W_i$。求解将哪些物品装入背包可使价值总和最大。

基本思路

最基础的背包问题,特点是每种物品仅有一件,可以选择放或者不放.

$F[i, v]$ 表示前 $i$ 件物品恰放入一个容量为 $v$ 的背包可以获得的最大价值。则其状态转移方程便是：

$$
F[i, v]=\max \left{F[i-1, v], F\left[i-1, v-C_{i}\right]+W_{i}\right}
$$

存在两种情况:

如果不放第 $i$ 件物品，那么问题就转化为 “前 $i − 1$ 件物品放入容量为 $v$ 的背包中”，价值为 $F[i − 1, v]$；
如果放第 $i$ 件物品，那么问题就转化为 “前 $i − 1$ 件物品放入剩下的容量为 $v −C_i$ 的背包中”，此时能获得的最大价值就是$F[i − 1, v −C_i]$ 再加上通过放入第 $i$ 件物品获得的价值 $W_i$。

上述问题的伪代码:

int N, V;
// cv[i][0]是放第i件物品消耗的费用,cv[i][1]是放第i件物品的收益价值,其中i从1开始
int[][] cv = new int[N + 1][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++) {
        if (cv[i][0] <= j) {
            dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - cv[i][0]] + cv[i][1]);
        } else {
            dp[i][j] = dp[i - 1][j];
        }
    }
}
return dp[N][V];

注意❗: 外层枚举物品的数量,内层枚举背包的容量

初始化的细节问题

我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。

如果要求恰好装满背包，那么在初始化时除了$F[0]$ 为 $0$，其它$F[1..V]$ 均设为 $−∞$，这样就可以保证最终得到的 $F[V]$ 是一种恰好装满背包的最优解。
如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将 $F[0..V]$全部设为 0。

这是为什么呢？可以这样理解：初始化的 $F$ 数组事实上就是在没有任何物品可以放入背包时的合法状态。

如果要求背包恰好装满，那么此时只有容量为 $0$ 的背包可以在什么也不装且价值为 $0$ 的情况下被“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，应该被赋值为 $-∞$ 了。
如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为 $0$，所以初始时状态的值也就全部为 $0$了。

优化空间复杂度

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

优化空间复杂度

由于dp[i][j]是由dp[i-1][j]和dp[i-1][j-cv[i][0]]两个子问题递推而来，可以通过在每次主循环中通过递减背包容量的遍历方式计算dp[j],这样就可以保证计算dp[j]的时候dp[j-cv[i][0]]保存的是dp[i-1][j-cv[i][0]]的值。

伪代码：

int N, V;
// cv[i][0]是放第i件物品消耗的费用,cv[i][1]是放第i件物品的收益价值,其中i从1开始
int[][] cv = new int[N + 1][2];
int dp[] = new int[V + 1];
dp[0][0] = 0;
for (int i = 1; i <= N; i++) {
    for (int j = V; j >= 0; j--) {
        if (cv[i][0] <= j) {
            dp[j] = Math.max(dp[j], dp[j - cv[i][0]] + cv[i][1]);
        }
    }
}
return dp[V];

相关题目练习

题目URL

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 $v_i$，价值是 $w_i$。

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

输入格式

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

接下来有 N 行，每行两个整数 $v_i$,$w_i$，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式

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

数据范围

$0<N,V≤10000<N,V≤1000$

$0<vi,wi≤10000<vi,wi≤1000$

输入样例

输出样例：

题目解法

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[][] vw = new int[N + 1][2];
        for (int i = 1; i <= N; i++) {
            // 体积
            vw[i][0] = sc.nextInt();
            // 价值
            vw[i][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++) {
            // 枚举背包的容量
            for (int j = 0; j <= V; j++) {
                // 如果当前物品的体积小于背包的剩余容量
                if (vw[i][0] <= j) {
                    // 可以选择当前的物品加入背包或者不加入背包
                    // 不加入背包时:问题转化成i-1件物品装入容量为j的背包的子问题
                    // 加入背包时:问题转化成i-1件物品装入容量为j-vw[i][0]的背包的子问题
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - vw[i][0]] + vw[i][1]);
                } else {
                    // 如果当前物品的体积大于背包的容量,那么不能装入,所以问题转化成
                    // i-1件物品装入容量为j的背包的子问题
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        // 返回N件物品,背包容量为V的装入的最大价值
        System.out.println(dp[N][V]);
    }
}

空间复杂度优化

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 [][]vw=new int[N+1][2];
        for(int i=1;i<=N;i++){
            vw[i][0]=sc.nextInt();
            vw[i][1]=sc.nextInt();
        }
        
        int dp[]=new int[V+1];
        dp[0]=0;
        for(int i=1;i<=N;i++){
            // 注意01背包的空间复杂度优化时需要容量从后往前遍历
            for(int j=V;j>=0;j--){
                if(vw[i][0]<=j){
                    dp[j]=Math.max(dp[j],dp[j-vw[i][0]]+vw[i][1]);
                }
            }
        }
        System.out.println(dp[V]);
    }
}

参考文献

崔添翼:背包九讲