01背包问题

20240220算法入门👉🏻AcWing

问题描述

有n件物品和一个最大容积为V的背包。第i件物品的体积是v[i]，得到的价值是w[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

代码详解

学习参考：AcWing 2. 01背包问题(看这篇就完事)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <iostream>
using namespace std;

//01背包特点：每件物品只能使用一次。
//求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大，输出最大价值。

const int N = 1024;
int n, V;//n件物品，背包容量是V
int v[N], w[N];//第i件物品体积v[i]，价值w[i]
int dp[N][N];//默认初始值为0/全局变量默认为0

int main(int argc, char *argv[]) {
	//初始化
  cin >> n >> V;
	for(int i = 1; i <= n; i++)
		cin >> v[i] >> w[i];
  //动态规划
	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][j] = max(dp[i][j], dp[i-1][j-v[i]]+w[i]);
		}
	}
	cout << dp[n][V] <<endl;
	return 0;
}

想要解释这段代码的思路，核心就是理解其动态规划状态转移方程： $$ dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]]+w[i]); $$ dp数组示例(3件物品，容量最大为4)：

该二维数组每一项值dp[i][j]均表示在从下标[0,i]的物品里符合要求的任取后放进容量为j的背包下最大的价值总和。换句话理解就是表格中的每一项都是当前情况下的最优解(最大价值)。

值得强调的是在构建二维数组时要考虑i=0和j=0的情况，即什么都不选和背包容量为0，方便状态转移方程进行递推，易得第一行和第一列值均为0。

接下来就是按行依次进行递推，考虑每格的值就两种情况：

1. 不放入物品i，就相当于和之前情况无变化，即此情况下最优与上面一格相同(dp[i-1][j])。

2. 放入物品i，需先考虑能否放入(主要比较容积，不能放入的话回到情况1)，能放入的话无非就是比较放入后的价值和不放入的价值哪个更大，即状态转移方程中max(dp[i-1][j],xxxx)部分可以理解了，现在就是如何计算放入当前物品后的最优价值。

   因为我要放入该物品i，则还剩下的背包空间为j-v[i]，则要找到背包空间为j-v[i]下的不含物品i的最优价值即dp[i-1][j-v[i]]，再加上物品i的价值即为所求，状态转移方程dp[i-1][j-v[i]]+w[i]部分由此而来。

由此完成所有递推，dp[n][V]即为最终的最大价值。

👉🏻学习参考链接中有提到优化版，不多赘述，其思路主要是原方案下只用到了当前行(i)和前一行(i-1)，因此将二维简化到了一维，将每一次大循环后所得到的dp[N]理解为原先二维中的某一行即可 。原先二维可以理解为把每一步物品选择后的最优价值都进行了存储，优化版本则放弃了存储的冗余，每一步递推都在原数组上直接进行并覆盖。