背包九讲之完全背包问题

2021-03-23

[toc]

说明:

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

完全背包问题

题目

有 $N$ 种物品和一个容量为 $V$ 的背包，每种物品都有无限件可用。放入第 $i$ 种物品
的费用是 $C_i$，价值是 $W_i$。求解：将哪些物品装入背包，可使这些物品的耗费的费用总和不超过背包容量，且价值总和最大

基本思路

与01背包问题的不同之处在于每种物品有无限件,从每种物品的角度考虑,与它相关的 策略不再是取或者不取两种状态,而是有取$0$件、取$1$件、取$2$件……直至取$⌊V/C_i⌋$ 件等许多种.

按照01背包的思路，令 $F[i, v]$ 表示前 $i$ 种物品恰放入一个容量为 $v$的背包的最大价值(收益)。仍然可以按照每种物品不同的策略写出状态转移方程：
$$
F[i, v]=\max \left{F\left[i-1, v-k C_{i}\right]+k W_{i} \mid 0 \leq k C_{i} \leq v\right}
$$

这跟 01 背包问题一样有 $O(VN)$ 个状态需要求解，但求解每个状态的时间已经不是常数了,因为需要遍历k为$1、2、3… \frac{v}{c_{i}}$ 时的状态，求解状态 $F[i, v]$ 的时间是$O\left(\frac{v}{C_{i}}\right)$ . 总的复杂度可以认为是 $O\left(N V \sum \frac{V}{C_{i}}\right)$

上述问题的伪代码

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++) {
        for (int k = 0; k * cv[i][0] <= j; k++) {
            dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * cv[i][0]] + k * cv[i][1]);
        }
    }
}
return dp[N][V];

注意❗: 外层i枚举物品的数量,内层j枚举背包的容量，最内层k枚举选择i的件数

注意❗❗❗: 转移方程为dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * cv[i][0]] + k * cv[i][1]) max函数里面是dp[i][j]和dp[i - 1][j - k * cv[i][0]] + k * cv[i][1]这两项, 切记!切记!

一个简单有效的优化

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

$O(VN)$的算法

伪代码：


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=0; i<=v; i++){
    for(int j=1; j<=N;j++){
        if(cv[j][0]<=j){
            dp[i] = Math.max(dp[i], dp[j-cv[j][0]]+cv[j][1]);
        }
    }
}
// 这两个循环的顺序可以交换,交换顺序前的
for(int i=1; i<=N; i++){
    for(int j=0; j<=V; j++){
        if(cv[i][0]<=i){
            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++) {
            // 枚举背包的容量j
            for (int j = 0; j <= V; j++) {
                // 枚举选择第i种物品的数量k
                for (int k = 0; k * vw[i][0] <= j; k++) {
                    // dp[i][j]的值是:{选择k件第i种物品时}与{选择其他数量的第i种物品}的两者的最大值
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * vw[i][0]] + k * vw[i][1]);
                }
            }
        }
        // 返回N件物品,背包容量为V的装入的最大价值
        System.out.println(dp[N][V]);
    }
}

参考文献

崔添翼:背包九讲