「动态规划」01背包问题

01背包、分组背包问题

题目

来源acwing 2. 01背包问题

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

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

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

输出最大价值。

初步思路

二维动态规划

$f[i][j]$ 表示只考虑前 $i$ 个物品，总体积是 $j$ 情况下，总价值最大是多少？

状态转移方程：

$$f[i][j] = max\{f[i-1][j-v_i] + w_i, f[i-1][j]\}$$

1. 选第 $i$ 个物品 $f[i - 1][j-v_i]$

2. 不选第 $i$ 个物品 $f[i-1][j]$

然后两种情况求最大值

初始化：

$$f[0][0] = 0$$

最终结果：

$$max\{f[n][0]\cdots f[n][v]\}$$

代码：

import java.util.*;

class Main {
    private static int N = 1010;
    private static int f[][] = new int[N][N];
    private static int w[] = new int[N];
    private static int v[] = new int[N];

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int m = cin.nextInt();
        for (int i = 1; i <= n; i++) {
            v[i] = cin.nextInt();
            w[i] = cin.nextInt();
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                f[i][j] = f[i - 1][j];
                if (j >= v[i]) {
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - v[i]] + w[i]);
                }
            }
        }
        System.out.println(f[n][m]);
    }
}

优化

因为状态转移只涉及到 $f[i]$ 和 $f[i-1]$

可以考虑使用一维数组，优化空间占用。

import java.util.Scanner;

class Main {
    // 一维数组 来优化
    private static int N = 1010;
    private static int w[] = new int[N];
    private static int v[] = new int[N];
    private static int f[] = new int[N];

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int m = cin.nextInt();
        for (int i = 1; i <= n; i++) {
            v[i] = cin.nextInt();
            w[i] = cin.nextInt();
        }
        for (int i = 1; i <= n; i++) {
            for (int j = m; j >=v[i]; j--) {
                //
                f[j] = Math.max(f[j], f[j-v[i]] + w[i]);
            }
        }
        // f[m]实际上是体积≤m的最大价值，就是答案
        System.out.println(f[m]);
    }
}

注意

1. 二层循环中，必须从后向前，即从 $m$ 到 $v[i]$ ，因为转移到 $f[i][j]$ 用的是 $f[\bold{i-1}][j-v_i]$ 状态，而从前向后循环时，每次用的实际上是 $f[\bold{i}][j-v_i]$

ps: 这里表述不对，不会每次都用，但是当 $f[j-v_i]$ 在本轮被更新过后，就可能使用了。

滚动数组失去了正确性。

这反而是完全背包问题的转移方程

2. 之前提到，最终结果应当是 $max\{f[n][0]\dots f[n][v]\}$ ，如果对 $dp$ 数组每个元素初始化为0， $f[m]$ 实际上是 $V\le m$ 的最大价值，就是答案

   解释：

   若 $dp$ 数组全部初始化为0, $dp[i] = 0$

   假设在容量 $k$ 取到最大值, $dp[k]=maxval$ ;

   $dp[m]$ --> $dp[m - v[1]] + w[1]$
   由于初始化 $dp[m - v[1]] = 0$
   同理 $dp[k] = dp[k-v[1]] + w[1] = dp[0] + w[1] = w[1]$

   一般化 $dp[m - k] = 0$ --> $dp[m] = dp[k] = maxval$

   举个具体的例子
   一个背包容量为 $6$ ，目前只有 $2$ 个物品可供选择
   $v[1]=5,w[1]=1000$
   $v[2]=4,w[2]=10$

   $dp[1][4]=maxVal=1000$
   $dp[1][6] = dp[1][6-5] + w[1] = dp[1][1]+1000 = 1000$
   $dp[1][1]$ 初始化为 $0$ ，但实际上 $dp[1][1]$ 并无实际意义：因为容量为 $1$ 的状态不存在

   反之，如果只将 $dp[0]=0$
   其余赋为最小负值 $dp[i]=-INF$

   便可保证 $dp[m]$ 的值是从 $dp[0]$ 处转移过来，即容量恰好等于 $m$ 的时候的最大价值。

多重背包

题目:acwing 4.多重背包问题1

多重背包相比01背包，多了一个限制条件：

第 $i$ 个物品最多有 $s_i$ 件

在01背包的基础上多一重循环

import java.util.Scanner;

class Main {
    // 一维数组 来优化
    private static int N = 1010;
    private static int w[] = new int[N];
    private static int v[] = new int[N];
    private static int f[] = new int[N];
    private static int s[] = new int[N];

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int m = cin.nextInt();
        for (int i = 1; i <= n; i++) {
            v[i] = cin.nextInt();
            w[i] = cin.nextInt();
            s[i] = cin.nextInt();
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = m; j >= 0; --j) {
                for (int k = 1; k <= s[i] && k*v[i] <= j; ++k) {
                    f[j] = Math.max(f[j], f[j-k*v[i]] + k*w[i]);   
                }
            }
        }
        
        System.out.println(f[m]);
    }
}

上述算法时间复杂度 $O(n^3)$

下面考虑进行优化

如何转化为0-1背包问题?

1. 直接拆分：将每种物品拆成 $s_i$ 个，每一份视作一个独立的物品。转化为0-1背包问题。

这样做复杂度太高

---

2. 二进制拆分

原理：$S_i$ 件物品最少需要 $log_2S_i$ 个数可以表示出

举个栗子🌰

15件物品，可以分成 $\lfloor log_215 \rfloor=4$ 堆，每堆分别有 $2^0$ , $2^1$ , $2^2$ , $2^3$ , 即1、2、4、8个。

任何一个属于 $[0, 15]$ 的数字都可以用这四堆来表示。

Ex：我选择了第 1、3堆，就相当于选择了5件该物品。

import java.util.Scanner;

class Main {
    private static int N = 12010;
    private static int M = 2010;
    private static int w[] = new int[N];
    private static int v[] = new int[N];
    private static int f[] = new int[M];

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int m = cin.nextInt();
        int cnt = 1;
        for (int i = 1; i <= n; i++) {
            int a = cin.nextInt();
            int b = cin.nextInt();
            int s = cin.nextInt();
            for (int k = 1; k <= s; k *= 2) {
                v[cnt] = a * k;
                w[cnt++] = b * k;
                s -= k;
            }
            if (s > 0) {
                v[cnt] = a * s;
                w[cnt++] = b * s;
            }
        }
        n = cnt - 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = m; j >= v[i]; --j) {
               f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
            }
        }
        
        System.out.println(f[m]);
    }
}

分组背包

9. 分组背包问题

每组物品最多选一个

有个物品组的概念之后，每组物品的选择状态有 $s_i+1$ 种：不选、选第1个、选第2个……选第 $s_i$ 个

多重背包问题是分组背包的特殊情况

因此分组背包只能去做三重循环,没法优化。

状态转移方程如下：

$f[i][j]= max\{f[i-1][j], f[i][j-v_1]+w_1, f[i][j-v_2]+w_2+\cdots+f[i][j-v_{s_i}] + w_{s_i}\}$

题目

输入格式

代码

import java.util.*;

class Main{
    static final int N = 110;
    static int[] f = new int[N];
    static int[] v = new int[N];
    static int[] w = new int[N];
    
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n, m;
        n = cin.nextInt();
        m = cin.nextInt();
        for (int i = 0; i < n; ++i) {
            int s;
            s = cin.nextInt();
            for (int j = 0; j < s; ++j) {
                v[j] = cin.nextInt();
                w[j] = cin.nextInt();
            }
            for (int j = m; j >= 0; --j) {
                for (int k = 0; k < s; ++k) {
                    if (j >= v[k]) f[j] = Math.max(f[j], f[j - v[k]] + w[k]);
                }
            }
        }
        System.out.print(f[m]);
    }
}

注意，一定要判断 $j\ge v[k]$

后话

一定要注意，多重背包是分组背包的特殊情况(个人觉得更像是0-1背包的特殊情况)，每一组最多选 $s_i$ 个物品，也就是说可以选0个、1个、2个… $s_i$ 个，可以退化为0-1背包问题。也可以用二进制优化

但是，基本的分组背包问题，每一组内的物品是互斥的，每组最多选1个物品。这与0-1背包问题是不一样的

完全背包问题则是在多重背包的基础上，每一组物品数量是无限的

关于背包问题的一些很棒的讲解

相关例题

0-1背包

494. 目标和

题目及分析

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

考虑将添加负号的部分的和记为 $neg$ ，总和为 $sum$ ，正数部分的和为 $sum-neg$ ，则表达式的值为 $(sum-neg)-neg=target$

$neg=\frac{sum-target}{2}$ ，如果 $sum < target$ 或者 $sum-target$ 不是偶数，都不符合要求，直接返回 $0$ 即可

那么问题就转变成了，求出使得背包容量为 $neg$ 的合法方案数量，每种物品只有一个

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int diff = sum - target;
        if (diff < 0 || diff % 2 != 0) {
            return 0;
        }
        int neg = diff / 2;
        int[] dp = new int[neg + 1];
        dp[0] = 1;
        for (int num : nums) {
            for (int j = neg; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }
        return dp[neg];
    }
}

分组背包

1155. 掷骰子的N种方法

「每组物品必须选一个」

注意与「每组物品最多选一个」的区别

题目及分析

这里有 n 个一样的骰子，每个骰子上都有 k 个面，分别标号为 1 到 k 。

给定三个整数 n , k 和 target ，返回可能的方式(从总共 kn 种方式中)滚动骰子的数量，使正面朝上的数字之和等于 target 。

答案可能很大，你需要对 109 + 7 取模 。

示例

输入：n = 2, k = 6, target = 7
输出：6
解释：你扔两个骰子，每个骰子有6个面。
得到7的和有6种方法1+6 2+5 3+4 4+3 5+2 6+1。

分析

分组背包问题，每组物品有 $k$ 个，重量分别为 $1，2，3 \dots k$ 。现在每组必须选择一个物品，求总重量为 $target$ 的方案数

转移方程如下

$dp[i][j] = \sum_{1\leq t \leq k}dp[i-1][j-t],j\geq t$

代码

二维DP

class Solution {
    static final int MOD = (int)1e9+7;
    public int numRollsToTarget(int n, int k, int target) {
        // 分组背包
        int[][] f = new int[n + 1][target + 1];
        f[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = target; j >= 0; --j) {
                for (int t = 1; t <= k; ++t) {
                    if(j >= t) f[i][j] = (f[i][j] + f[i - 1][j - t]) % MOD;
                }
            }
        }
        return f[n][target];
    }
}

滚动数组优化空间占用

class Solution {
    static final int MOD = (int)1e9+7;
    public int numRollsToTarget(int n, int k, int target) {
        // 分组背包
        int[] f = new int[target + 1];
        f[0] = 1;
        for (int i = 0; i < n; ++i) {
            for (int j = target; j >= 0; --j) {
                f[j] = 0; // 如果不置0，则求出的是当前骰子可以为0点，即不投掷的情况下的方案数
                for (int t = 1; t <= k; ++t) {
                    if(j >= t) f[j] = (f[j] + f[j - t]) % MOD;
                }
            }
        }
        return f[target];
    }
}

---

📔博文图谱

提及本博文的链接

• 「动态规划」完全背包问题

• 图论：单源最短路径问题-Bellma ford