【动态规划】01背包问题

前言

动态规划是一种非常常见的算法，不论是在我们平时刷题的过程中还是在竞赛中，总会见到动态规划的身影，而动态规划又分为很多种，其中01背包问题是非常典型的一类动态规划问题。如果大家之前没有了解过动态规划，建议大家先去学习学习动态规划，直接开始01背包问题是由一定难度的。对于01背包问题，我花了两天的时间研究，这篇文章我将详细为大家介绍一下01背包问题。

什么是动态规划

动态规划（Dynamic Programming，简称DP）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

动态规划的基本思想是将一个复杂的问题分解为若干个子问题，这些子问题具有无后效性，即某个阶段的状态一旦确定，则此后过程的演变不再受此前各种状态及决策的影响。同时，这些子问题往往不是互相独立的，不同的子问题之间常常存在相互联系。因此，在求解时，对于每一个子问题只求解一次，并将其结果存储起来，避免对同一个子问题的重复求解。

动态规划的步骤如下：

1. 定义状态表示。我认为这一步是动态规划所有步骤中最重要的一步，首先需要确定 dp 数组中的每一个元素代表的是什么意思，只有正确的表示出了状态表示才能继续下面的操作。
2. 推导状态转移方程。以最近的一个状态为标准，根据该状态的前或者后面的状态来推导出当前状态的 dp 值。
3. 初始化。对于一些情况，可能会多创建一些行或者列，为了防止这些多出来的行和列对我们填表的正确性的影响，以及防止数组下标的越界问题，往往需要在填表之前对 dp 表进行初始化操作。
4. 填表。根据状态转移方程对 dp 表中的每个位置进行填值。
5. 确定返回值。确定 dp 数组中的哪个元素是我们需要的。

什么是01背包问题

01背包问题是一种典型的动态规划问题。它描述的是：给定一组物品，每种物品都有自己的重量和价值，在限定的总重量内，如何选择，才能使得物品的总价值最大。问题的名字中的“01”表示每种物品只有一件，可以选择放（1）或不放（0）入背包中。

解决01背包问题的一个常用方法是动态规划。首先，我们需要定义状态，通常用一个二维数组dp[i][j]表示前i个物品放入容量为j的背包中能获得的最大价值。然后，我们需要找到状态转移方程，也就是根据已知的状态推导出新的状态。最后，我们通过填表的方式，从初始状态开始，逐步计算出最终状态，也就是我们所求的答案。

光看理论可能比较难以理解什么是01背包问题，那么我们来看一道题目：

01背包

[模板]01背包

题目要求

描述
你有一个背包，最多能容纳的体积是V。

现在有n个物品，第i个物品的体积为vi ,价值为wi 。

（1）求这个背包至多能装多大价值的物品？
（2）若背包恰好装满，求至多能装多大价值的物品？
输入描述：
第一行两个整数n和V，表示物品个数和背包体积。
接下来n行，每行两个数 vi 和 wi ，表示第i个物品的体积和价值。

1 ≤ n,V,vi,wi <= 100

输出描述：
输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。

示例1

输入：
3 5
2 10
4 5
1 4
输出：
14
9
说明：
装第一个和第三个物品时总价值最大，但是装第二个和第三个物品可以使得背包恰好		装满且总价值最大。 

示例2

输入：
3 8
12 6
11 8
6 8
输出：
8
0
说明：
装第三个物品时总价值最大但是不满，装满背包无解。 
备注：

要求O(nV)的时间复杂度，O(V)空间复杂度

第一问做题思路

我们可以就使用循环来将所有可能的组合列举出来，然后将每种组合的体积和和价值和求出来，在保证体积不超过背包容积的条件下的最大价值，这样做是可以做出来的，但是这样做的时间复杂度会比较高，为什么呢？因为使用穷举的方法做出来的话会有非常多的重复计算。而我们使用动态规划的话，在遍历完成 i 个物品之后，会将前 i 个物品的选择情况的在背包容积之内的最大价值记录下来，然后我们再继续遍历剩下的物品的时候就只需要在这个记录的数字上进行计算就可以了，这样就减少了很多的重复计算。

1. 确定状态表示

我们首先从一维的 dp 数组开始，dp[i] 表示从前 i 个物品中选择装入背包，使得背包中的物品的体积小于背包容量，并且背包中的总价值最大，那么从这个状态表示中如何推导出状态转移方程呢？我们从最近的一个状态进行推导 —— dp[i]，对当前状态再进行细分的话，就可以分为当前第 i个位置的物品没有被选择/被选择，没有被选择的话，那么 dp[i] 中的值就是 dp[i-1]，但是如果当前物品需要装进背包的时候，我们如何确定背包的容量是否能够装进这个第 i 个物品呢？很显然，一维 dp 表是无法推导出状态转移方程的。所以我们将 dp 表定义为二维的，dp[i][j] 表示从前 i 个物品中选择物品装入背包容量为 j 时的背包中物品的最大价值。

2. 推导状态转移方程

根据最近的一个状态推导出状态转移方程 dp[i][j]，如果第 i 个物品选择不放入背包的话，那么 dp[i][j] 就是从前 i-1 个物品中选择出总体积不大于 j 的物品的最大价值也就是 dp[i][j] = dp[i-1][j]，如果第 i 个物品选择装入背包的话， 需要满足条件，就是背包容量 j 需要大于等于第 i 个物品的体积 v[i]，如果满足这条件，那么第 i 个物品就可以装入背包，问题是第 i 个位置选择装入时的 dp[i][j] 值为多少呢？因为当前状态的背包的最大容量为 j，要想保证装入第 i 个位置的物品之后的背包不会装不下，那么就需要保证在装第 i-1 个位置的物品的时候，要留下大于等于 v[i] 的空间，也就是在装第 i-1 个位置的时候，背包的最大容量为 j-v[i]，但是也不能让选择第 i-1 个位置的物品的时候背包的容积太小了，因为背包容积越小的话，能装的物品就越少，背包中物品的价值就无法达到最大。所以当第 i 个位置的物品选择装入的话，dp[i][j] 的值就为 dp[i-1][j - v[i]] + w[i]。那么 dp[i][j] 的最终值就是第 i 个位置的物品选择装入时候的 dp[i][j] 的值和选择不装入第 i 个位置的物品的 dp[i][j] 值的最大值。dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i])。

3. 初始化

这道题目给出了 1 ≤ n,V,vi,wi <= 100，也就是 dp 数组的行是从 1 开始的，列也是从 1 开始的，就意味着如果我们不映射下标值的话，就会多出来一行和一列，在这里我们也不选择下标的映射，因为通过这个多出来的一行和一列可以方便我们进行填表，因为填表时候的 dp[i][j] 需要依赖于 dp[i-1][j] 和 dp[i-1][j - v[i]]，当映射数组下标的话，i 和 j 都从 0，开始，那么当 i 为 0 的时候，就会发生下标越界的情况，我们可以在填表之前先对第一行进行单独的填值，但是不建议这样做，因为通过多一行多一列的情况，我们可以将这一次单独的填值统一放进循环中进行，并且这种多创建出一行和一列的 dp 表是非常实用的。

那么对于这多出来的一行和一列中的每个值该怎么办呢？我们需要保证这一行和一列的值不会对其他位置的填值的正确性造成影响，第 0 行代表的是从前 0 和物品中选择物品装入背包容量为1，2，3…的背包中使得价值最大时候的价值，但是既然是 0 个物品，那么背包中的总价值就是 0，所以第一行的值都为 0，对于第 0 列的意思就是从前 i 个位置的物品中选择物品装入背包容量为 0 的背包中，使得背包中的物品的总价值最大时的价值，既然背包容量为 0，那么一个物品就装不下，那么背包中物品的最大价值就是 0。

4. 填表和确定返回值

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        //从键盘中读取n，V和v数组、w数组
        int n = s.nextInt(), V = s.nextInt();
        int[] v = new int[n + 1], w = new int[n + 1];
        for (int i = 1; i < n; i++) {
            v[i] = s.nextInt();
            w[i] = s.nextInt();
        }
        //确定状态表示为dp[i][j]为从前i个位置（包括i）位置的物品中选择物品装入背包容积
        //为j时的背包中价值最大的值
        //创建dp表
        int[][] dp = new int[n + 1][V + 1];
        //初始化：因为数组中的默认值是0，所以这里不需要进行其他的操作
        //填表
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= V; j++) {
                //第i个位置的物品不选择的情况一定存在,所以我们先处理不选择的请跨国
                dp[i][j] = dp[i-1][j];
                //再来判断第i个位置的物品是否可以装入背包,取两种情况的最大值
                if (j >= v[i]) dp[i][j] = Math.max(dp[i][j],dp[i-1][j - v[i]] + w[i]);
            }
        }
        //确定返回值，返回的是在n个物品中选择物品装入背包容量为V的背包中物品的最大价值，
        //所以返回的值为dp[n][V]
        System.out.println(dp[n][V]);
    }
}

第二问做题思路

1. 确定状态表示

第二问和第一问状态表示不同的是，第二问求的是背包装满情况时背包中的物品的最大价值，所以对于第二问的状态表示就是 dp[i][j] 表示从前 i 个位置的物品中选择物品装入使得容量为 j 的背包恰好装满时的背包中所有物品的总价值。

2. 推导状态转移方程

第二问的状态表示虽然有区别，但是状态转移方程还是一样的，当第 i 个位置的物品选择不装入的时候的 dp[i][j] 为 dp[i-1][j]，但是当第 i 个位置的物品选择装入的时候，不仅需要此时背包的容量 j 大于等于第 i 个物品的体积 v[i] 还需要保证，在从 i 之前的物品中选择物品装入背包容量为 j-v[i] 的时候背包恰好装满的情况存在，也就是 dp[i-1][j - v[i]] 存在，然后就是 dp[i][j] 的最终值就是 max(dp[i-1][j],dp[i-1][j-v[i]] + w[i])。

3. 初始化

如何判断当背包容量为 j-v[i] 的时候选择物品装入背包恰好装满的情况存在呢？可以使用 0 吗？可以是可以，但是为了和 dp[0][0] 的 0 区别开，我们选择 -1 作为此状态不存在的情况，这里初始化同样是针对多出来的一行和一列进行初始化，当行为 0 时，表示的意义是从前 0 个位置的物品中选择物品装入背包容量为1，2，3…时的情况，这种情况是不存在的，所以第一行从第 1 列开始到最后一列的值初始为 -1；那么第 0 列的情况呢？第一列的意思表示的是从前1，2，3…个位置的物品中选择物品装入背包容量为 0 时的情况，因为背包的容量为 0，所以我们选择都不装，那么此时背包中的总价值都为0；而 dp[0][0] 则表示选择前 0 个位置的物品选择装入背包容量为 0 的情况，这时就选择不装入物品，此时背包中的总价值为0。

4. 填表和确定返回值

//状态表示为dp[i][j]为从前i个位置的物品中选择物品装入背包容积为j并且背包恰好装满
//时候的背包中物品总价值的最大值

//初始化
//因为前面使用了dp，我们可以再创建一个表，也可以对dp表进行修改
for (int i = 1; i <= V; i++) dp[0][i] = -1;
//填表
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= V; j++) {
        dp[i][j] = dp[i-1][j];
        if (j >= v[i] && dp[i-1][j - v[i]] != -1) dp[i][j] = Math.max(dp[i][j],dp[i-1][j - v[i]] + w[i]);
    }
}
//确定返回值，因为题目中要的是从n个物品中选择物品装入背包容积为V并且背包恰好装满
//时候的背包中的物品的最大价值，所以返回值为dp[n][V]，并且题目中说了如果不存在
//背包恰好装满的情况就返回0
System.out.println(dp[n][V] == -1 ? 0 : dp[n][V]);

第一问和第二问全部代码

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        //从键盘中读取n，V和v数组、w数组
        int n = s.nextInt(), V = s.nextInt();
        int[] v = new int[n + 1], w = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            v[i] = s.nextInt();
            w[i] = s.nextInt();
        }
        //确定状态表示为dp[i][j]为从前i个位置（包括i）位置的物品中选择物品装入背包容积
        //为j时的背包中价值最大的值
        //创建dp表
        int[][] dp = new int[n + 1][V + 1];
        //初始化：因为数组中的默认值是0，所以这里不需要进行其他的操作
        //填表
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= V; j++) {
                //第i个位置的物品不选择的情况一定存在,所以我们先处理不选择的请跨国
                dp[i][j] = dp[i-1][j];
                //再来判断第i个位置的物品是否可以装入背包,取两种情况的最大值
                if (j >= v[i]) dp[i][j] = Math.max(dp[i][j],dp[i-1][j - v[i]] + w[i]);
            }
        }
        //确定返回值，返回的是在n个物品中选择物品装入背包容量为V的背包中物品的最大价值，
        //所以返回的值为dp[n][V]
        System.out.println(dp[n][V]);

        //状态表示为dp[i][j]为从前i个位置的物品中选择物品装入背包容积为j并且背包恰好装满
        //时候的背包中物品总价值的最大值

        //初始化
        //因为前面使用了dp，我们可以再创建一个表，也可以对dp表进行修改
        for (int i = 1; i <= V; i++) dp[0][i] = -1;
        //填表
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= V; j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= v[i] && dp[i-1][j - v[i]] != -1) dp[i][j] = Math.max(dp[i][j],dp[i-1][j - v[i]] + w[i]);
            }
        }
        //确定返回值，因为题目中要的是从n个物品中选择物品装入背包容积为V并且背包恰好装满
        //时候的背包中的物品的最大价值，所以返回值为dp[n][V]，并且题目中说了如果不存在
        //背包恰好装满的情况就返回0
        System.out.println(dp[n][V] == -1 ? 0 : dp[n][V]);
    }
}

滚动数组优化

对于背包问题，往往可以进行一些优化，而这些优化往往是体现在空间上的优化，那么这个题目可以如何优化呢？首先我们填表的时候 dp[i][j] 需要依赖于 dp[i-1][j] 和 dp[i-1][j - v[i]]，也就是说，我们再填表的时候只需要知道第 i-1 行的数据就可以了，所以我们可以只使用两行数组就可以完成填表：

当第 i 行的数据填完之后，第 i-1 行的数据就不再需要了，我们就可以将第 i - 1行的数组移动到 i + 1 这个位置中，然后继续根据第 i 行的数据填写第 i + 1行的数据，当第 i + 1 行的数据填写完成之后，再将第 i 行的数据移动的第 i + 2 行，继续如此操作，最后就可以填写完成 dp[n][V] 的数据，这就叫做滚动数组优化。

优化代码：

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt(), V = s.nextInt();
        int[] v = new int[n + 1], w = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            v[i] = s.nextInt();
            w[i] = s.nextInt();
        }
        int[][] dp = new int[2][V + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= V; j++) {
                dp[i & 1][j] = dp[(i-1) & 1][j];
                if (j >= v[i]) dp[i & 1][j] = Math.max(dp[i & 1][j],dp[(i-1) & 1][j - v[i]] + w[i]);
            }
        }
        System.out.println(dp[n & 1][V]);
        
        for (int i = 1; i <= V; i++) dp[0][i] = -1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= V; j++) {
                dp[i & 1][j] = dp[(i-1) & 1][j];
                if (j >= v[i] && dp[(i-1) & 1][j - v[i]] != -1) dp[i & 1][j] = Math.max(dp[i & 1][j],dp[(i-1) & 1][j - v[i]] + w[i]);
            }
        }
        System.out.println(dp[n & 1][V] == -1 ? 0 : dp[n & 1][V]);
    }
}

一维数组优化

再观察我们可以发现当填 dp[i][j] 的时候只依赖于 dp[i-1][j] 和 dp[i-1][j-v[i]] 两个值，所以我们可以将 dp 数组优化为一维数组，每次填写第 i 行的数据的时候，用的都是第 i-1 行的数据：

但是只用一维数组的话需要注意了，就是填表的顺序不能是从左往右了，因为如果 dp[j-v[i]] 的值变化了的话，在填 dp[j] 的时候依赖的 dp[j-v[i]] 就不是原来的那个值了，所以我们优化为一维数组的时候需要修改填表顺序为从右到左填表：

优化代码:

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt(), V = s.nextInt();
        int[] v = new int[n + 1], w = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            v[i] = s.nextInt();
            w[i] = s.nextInt();
        }
        int[] dp = new int[V + 1];
        for (int i = 1; i <= n; i++) {
        //当j < v[i]的时候背包就装不下第i个物品了，所以前面的j也就不需要遍历了
            for (int j = V; j >= v[i]; j--) {
                dp[j] = Math.max(dp[j],dp[j - v[i]] + w[i]);
            }
        }
        System.out.println(dp[V]);
        
        for (int i = 1; i <= V; i++) dp[i] = -1;
        for (int i = 1; i <= n; i++) {
            for (int j = V; j >= v[i]; j--) {
                if (dp[j - v[i]] != -1) dp[j] = Math.max(dp[j],dp[j - v[i]] + w[i]);
            }
        }
        System.out.println(dp[V] == -1 ? 0 : dp[V]);
    }
}

分割等和子集

https://leetcode.cn/problems/partition-equal-subset-sum/description/

1. 题目要求

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

提示：

1 <= nums.length <= 200
1 <= nums[i] <= 100

2. 做题思路

这道题目的意思是将一个数组分割为两个数组，使得这两个数据中元素的和相等，换句话说就是让我们在整个数组中找是否存在和为整个数组所有元素和 sum 的一半的数字和。这样一看，将 sum / 2 看作是背包容量，然后数组中每个元素的值为体积，这道题的物品没有价值，所以我们就可以比对着上面的01背包模板来做这道题目。

3. 代码实现

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int n : nums) sum += n;
        //因为题目中说了数组中的元素都是正整数，所以当数组所有元素的和为奇数的时候，一定不会在数组找到
        //和为sum/2的数字和
        if (sum % 2 == 1) return false;
        int n = nums.length, aim = sum / 2;
        boolean[][] dp = new boolean[n + 1][aim + 1];
        for (int i = 0; i <= n; i++) dp[i][0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= aim; j++) {
                //第i个数字可以选择也可以不选择，两种情况任意一种为true，那么dp[i][j]的值就为true
                dp[i][j] = dp[i-1][j] || ((j >= nums[i-1]) && dp[i-1][j - nums[i-1]]);
            }
        }
        return dp[n][aim];
    }
}

一维数组优化

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int n : nums) sum += n;
        //因为题目中说了数组中的元素都是正整数，所以当数组所有元素的和为奇数的时候，一定不会在数组找到
        //和为sum/2的数字和
        if (sum % 2 == 1) return false;
        int n = nums.length, aim = sum / 2;
        boolean[] dp = new boolean[aim + 1];
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = aim; j >= nums[i-1]; j--) {
                //第i个数字可以选择也可以不选择，两种情况任意一种为true，那么dp[i][j]的值就为true
                dp[j] = dp[j] || dp[j - nums[i-1]];
            }
        }
        return dp[aim];
    }
}

文章来源地址https://www.toymoban.com/news/detail-852570.html

到了这里，关于【动态规划】01背包问题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！