前言
对0-1背包问题的二维dp数组以及一维dp数组的思路分析
来源:代码随想录 link
本文是我对01背包问题的理解,在本文中具体分析dp数组的形成过程,最核心的地方就是我对每种情况下的01背包问题给出了代码运行结果,便于读者理解。
重点解释了为什么一维dp数组的01背包问题为什么要倒叙遍历背包,以及为什么不能先遍历背包,只能先遍历物品。
1,一维dp数组为什么不能正序遍历书包?
因为正序遍历背包会导致同一个物品被放了两次,但是01背包要求同一物品只能被放一次。文章来源:https://www.toymoban.com/news/detail-775217.html
2,一维dp数组为什么不能先遍历背包?
因为能用一维dp数组解决01背包问题的原理就是先遍历物品时dp数组是一行一行形成的(具体过程正文中有结果显示
),下一行的数据只受到上一行数据的影响,因此可以只用一维数组去解决01背包问题,但是先遍历书包时dp数组时一列一列形成的(具体过程正文中有结果显示
),这二者本质上就是相悖的,如果要强行理解的话,就是如果先遍历背包时,只会往背包中放入一件物品(正文中有具体结果演示
)。文章来源地址https://www.toymoban.com/news/detail-775217.html
一、0-1背包问题
有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大
举例说明:假设背包最大重量为4,物品的重量以及价值如表所示:
重量weight | 价值value | |
---|---|---|
物品0 | 1 | 15 |
物品1 | 3 | 20 |
物品2 | 4 | 30 |
下面分别通过二维db数组以及一维dp数组进行分析。
二、二维dp数组01背包问题代码详解
1.递推关系式
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
dp[i][j]:从物品0到物品i中任意取,放入容量为j的背包,可放入物品的最大价值为dp[i][j]。
递推关系式的含义为:01背包问题可以分解为不放物品i和放物品i
即dp[i][j]为放物品i和不放物品i的得到的价值的最大值。
2.代码详解
2.1先遍历物品
根据代码随想录的介绍,二维dp数组的01背包问题先遍历物品还是先遍历背包均可。
如果先遍历物品,代码如下:
其中为了看到每次遍历后dp数组的变化,我将其打印输出,以便分析。
#include<iostream>
#include<vector>
#include <iomanip>
using namespace std;
//打印dp数组
void print_dparr(vector<vector<int>>& dp)
{
int row = dp.size();
int col = dp[0].size();
for (int i = 0;i < row;i++)
{
for (int j = 0;j < col;j++)
{
cout <<std::left << setw(2) << dp[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
void test_2_wei_bag_problem1() {
vector<int> weight = { 1, 3, 4 };
vector<int> value = { 15, 20, 30 };
int bagweight = 4;
// 二维数组
vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
// 初始化
for (int j = weight[0]; j <= bagweight; j++) {
dp[0][j] = value[0];
}
cout << "从物品0中取物品" << endl;
print_dparr(dp);
// weight数组的大小 就是物品个数
for (int i = 1; i < weight.size(); i++) { // 遍历物品
for (int j = 0; j <= bagweight; j++) { // 遍历背包容量
if (j < weight[i]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
cout << "从物品0"<<"到物品"<<i << "中取物品" << endl;
print_dparr(dp);
}
cout <<"最终结果为:"<< dp[weight.size() - 1][bagweight] << endl;
}
int main() {
test_2_wei_bag_problem1();
return 0;
}
代码运行结果如下:
dp数组形成过程
先遍历物品时,整个dp矩阵的下一行数据由上一行数据计算得到,
这也为使用一维dp数组解决01背包问题埋下伏笔
。
2.2.先遍历背包
同理先遍历背包再遍历物品可以得到相同结果,但是此时由于遍历顺序的改变,dp数组的形成过程发生了变化,首先附上代码:
#include<iostream>
#include<vector>
#include <iomanip>
using namespace std;
//打印dp数组
void print_dparr(vector<vector<int>>& dp)
{
int row = dp.size();
int col = dp[0].size();
for (int i = 0;i < row;i++)
{
for (int j = 0;j < col;j++)
{
cout <<std::left << setw(2) << dp[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
void test_2_wei_bag_problem1() {
vector<int> weight = { 1, 3, 4 };
vector<int> value = { 15, 20, 30 };
int bagweight = 4;
// 二维数组
vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
// 初始化
for (int j = weight[0]; j <= bagweight; j++) {
dp[0][j] = value[0];
}
// weight数组的大小 就是物品个数
// 遍历物品
int i;
for (int j = 0; j <= bagweight; j++) { // 遍历背包容量
for ( i = 1; i < weight.size(); i++) {
if (j < weight[i]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
cout << "从物品0到物品2中取物品放到容量为"<<j<<"的背包" << endl;
print_dparr(dp);
}
cout <<"最终结果为:"<< dp[weight.size() - 1][bagweight] << endl;
}
int main() {
test_2_wei_bag_problem1();
return 0;
}
代码运行结果如下:
dp数组形成过程
dp数组形成过程分析
由不同的遍历顺序的运行结果可知,先便利物品时dp数组是一行一行形成的,而先遍历背包时,dp数组是一列一列形成的。
如果先遍历物品,则其思想为从物品0到物品i中选物品放入容量为4的背包中得到的最大价值,其中i由0取到2。
如果先遍历背包,则其思想为从物品0到物品2中选物品放到容量为j的背包中得到的最大价值,其中j由0取到4。
根据递推关系式可知 dp[i][j] 与 i-1 行的 0 到 j-1 这些数据有关,这个思想对理解一维dp数组为什么倒序遍历很有用。
二维dp数组的01背包问题较好理解,下面介绍一维dp数组的01背包问题。
三、一维dp数组01背包问题代码详解
1.递推关系式
利用滚动数组的形式将二维数组降为一维数组,目前考虑先遍历物品的情况,后续分析先遍历背包的情况。
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
可以写成一维形式的原因在上述二维dp数组中其实已经略微阐述了一下,现在进行详细分析。
在上述分析中,我们知道dp[i][j] 只与 i-1 行的 0 到 j-1 这些数据有关,即dp矩阵的下一行数据只与上一行的一些数据有关,因此完全可以利用一维数组重复使用。
此时dp[j]的含义为:容量为j的背包可以背的最大价值。
2.代码详解
背包倒序遍历
下面分析一下先遍历物品时的一维dp数组解决01背包问题的代码,注意此时是倒序遍历背包:
#include<iostream>
#include<vector>
#include <iomanip>
using namespace std;
void print_dparr(vector<int>& dp)
{
int col = dp.size();
for (int j = 0;j < col;j++)
{
cout << std::left << setw(2) << dp[j] << " ";
}
cout << endl;
cout << endl;
}
void test_1_wei_bag_problem() {
vector<int> weight = { 1, 3, 4 };
vector<int> value = { 15, 20, 30 };
int bagWeight = 4;
// 初始化
vector<int> dp(bagWeight + 1, 0);
for (int i = 0; i < weight.size(); i++) { // 遍历物品
for (int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
cout << "从物品0到物品" << i << "取物品放到背包中" << endl;
print_dparr(dp);
}
cout <<"最终结果为:"<< dp[bagWeight] << endl;
}
int main() {
test_1_wei_bag_problem();
return 0;
}
运行结果为:
可以看到dp数组的形成过程与二维dp数组的形成过程一致,只不过此时的dp数组是一维的,把三个一维dp数组拼在一起便形成了二维dp数组的形式。
背包正序遍历
在一维dp数组求解01背包问题中很重要的一点就是书包的遍历顺序,此时书包的遍历顺序只能是倒序遍历,具体原因如下:
首先先将代码改成正序遍历的形式,具体代码在此不再赘述,只需要把上述代码的循环改成如下形式:
for (int i = 0; i < weight.size(); i++) { // 遍历物品
for (int j = 0; j <= bagWeight; j++) {// 遍历背包容量
if (j < weight[i]) continue;
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
cout << "从物品0到物品" << i << "取物品放到背包中" << endl;
print_dparr(dp);
}
代码运行结果如下:
可以发现结果不一样了,我们只看第一组数据来分析一下产生这种现象的原因,即从物品0中取物品放到背包中得到的结果为
正序遍历的结果:
0 15 30 45 60
倒序遍历的结果:
0 15 15 15 15
对比二者可以很容易发现以下现象:
30=15+15
45=30+15
60=45+15
从递推关系式出发:
初始化时dp[0] dp[1] dp[2]均为0,weight[0]=1,value[0]=15。
正序遍历的结果
dp[1] = dp[1 - weight[0]] + value[0] = dp[0] + 15 = 15
dp[2] = dp[2 - weight[0]] + value[0] = dp[1] + 15 = 30
倒序遍历的结果
dp[2] = dp[2 - weight[0]] + value[0] = dp[1] + 15 = 15
dp[1] = dp[1 - weight[0]] + value[0] = dp[0] + 15 = 15
下面这段话是理解一维dp数组的核心之处
可以发现正序遍历时计算 dp[2] 时把 dp[1]=15 加上去了,意味着物品0被放入了两次,但实际上加的应该是dp[1]=0 。换种方式理解就是dp[2]的正确计算方式应该是上一行的dp[1]加上15,而如果正序遍历的话,便使得dp[1]的值发生了改变,此时计算的是本行的dp[1]加上15。
因此需要倒序遍历使得每次取得状态不会和之前取得状态重合,这样每种物品就只取一次了。
3.先遍历背包
上述代码及分析均基于先遍历物品,现在分析先遍历背包时的情况。首先从上述分析中我们可以知道,先遍历背包时,二维dp数组是一列一列形成的,但是此时我们用一维dp数组时,我们只能按行形成dp数组,所以只能先遍历物品。
如果非要先遍历背包,可以将上述代码中的循环代码写成如下形式:
for (int j = bagWeight; j >= 0; j--) {
for (int i = 0; i < weight.size(); i++) { // 遍历物品
if (j < weight[i]) continue;
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
cout << "背包容量为" << j << "时的结果" << endl;
print_dparr(dp);
}
运行结果如下:
首先结果是错误的,这是由于先遍历背包时我们每次只往背包中放入一件物品,所以在背包容量为4时的结果为:
0 0 0 0 30
我们只需要知道先遍历书包跟一维dp数组解决01背包问题的原理相悖,因为根据上述的dp数组形成过程可以知道,先遍历书包的二维dp数组是一列一列往后形成的,而一维dp数组解决01背包问题的原理是由于dp数组可以按行去生成,这两者从本质上就是相悖的,没有讨论的必要。
总结
以上就是我对01背包问题的理解,最核心的地方就是我对每种情况下的01背包问题给出来代码运行结果,便于读者理解。
对于二维dp数组的01背包问题不多赘述,比较好理解。重点在于一维dp数组的01背包问题为什么要倒序遍历背包,以及为什么不能先遍历背包,只能先遍历物品。
1,一维dp数组为什么不能正序遍历书包?
因为正序遍历背包会导致同一个物品被放了两次,但是01背包要求同一物品只能被放一次。
2,一维dp数组为什么不能先遍历背包?
因为能用一维dp数组解决01背包问题的原理就是先遍历物品时dp数组是一行一行形成的(具体过程正文中有结果显示
),下一行的数据只受到上一行数据的影响,因此可以只用一维数组去解决01背包问题,但是先遍历书包时dp数组时一列一列形成的(具体过程正文中有结果显示
),这二者本质上就是相悖的,如果要强行理解的话,就是如果先遍历背包时,只会往背包中放入一件物品(正文中有具体结果演示
)。
到了这里,关于0-1背包问题思路分析,重点解释一维dp数组的01背包问题为什么要倒序遍历背包,以及为什么不能先遍历背包,只能先遍历物品的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!