0-1背包问题思路分析,重点解释一维dp数组的01背包问题为什么要倒序遍历背包,以及为什么不能先遍历背包,只能先遍历物品

这篇具有很好参考价值的文章主要介绍了0-1背包问题思路分析,重点解释一维dp数组的01背包问题为什么要倒序遍历背包,以及为什么不能先遍历背包,只能先遍历物品。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


前言

对0-1背包问题的二维dp数组以及一维dp数组的思路分析
来源:代码随想录 link

本文是我对01背包问题的理解,在本文中具体分析dp数组的形成过程,最核心的地方就是我对每种情况下的01背包问题给出了代码运行结果,便于读者理解。
重点解释了为什么一维dp数组的01背包问题为什么要倒叙遍历背包,以及为什么不能先遍历背包,只能先遍历物品。

1,一维dp数组为什么不能正序遍历书包?
因为正序遍历背包会导致同一个物品被放了两次,但是01背包要求同一物品只能被放一次。

2,一维dp数组为什么不能先遍历背包?
因为能用一维dp数组解决01背包问题的原理就是先遍历物品时dp数组是一行一行形成的(具体过程正文中有结果显示),下一行的数据只受到上一行数据的影响,因此可以只用一维数组去解决01背包问题,但是先遍历书包时dp数组时一列一列形成的(具体过程正文中有结果显示),这二者本质上就是相悖的,如果要强行理解的话,就是如果先遍历背包时,只会往背包中放入一件物品(正文中有具体结果演示)。
文章来源地址https://www.toymoban.com/news/detail-775217.html


一、0-1背包问题

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大
01背包为什么要倒着循环,动态规划

举例说明:假设背包最大重量为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数组形成过程

01背包为什么要倒着循环,动态规划

先遍历物品时,整个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数组形成过程

01背包为什么要倒着循环,动态规划

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;
}

运行结果为:

01背包为什么要倒着循环,动态规划

可以看到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);
    }

代码运行结果如下:

01背包为什么要倒着循环,动态规划

可以发现结果不一样了,我们只看第一组数据来分析一下产生这种现象的原因,即从物品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);
    }

运行结果如下:

01背包为什么要倒着循环,动态规划

首先结果是错误的,这是由于先遍历背包时我们每次只往背包中放入一件物品,所以在背包容量为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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法训练第四十二天|01背包问题 二维 、01背包问题 一维、416. 分割等和子集

    视频链接:https://www.bilibili.com/video/BV1cg411g7Y6/ 参考:https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.html 对于面试的话,其实掌握01背包,和完全背包,就够用了,最多可以再来一个多重背包。 而完全背包又是也是01背包稍作变化而来,即:完全

    2024年02月01日
    浏览(46)
  • 动态规划DP之背包问题3---多重背包问题

    目录 DP分析: 优化:  二进制优化 例题:         01背包是每个物品只有一个,完全背包问题是每个物品有无限个。         那么多重背包问题就是 每个物品有有限个 。 有 N 种物品和一个容量是 V 的背包。 第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。 求解

    2024年03月20日
    浏览(49)
  • 【DP】学习之背包问题

    2. 01背包问题 - AcWing题库 记忆化搜索  这里补个图,DFS是自顶向下推的 dp的递推是从下往上 用一维数组代替二维数组  进一步优化 这里m从m走到0,的原因是只让每个物品最多拿一次。 如果正序枚举体积,就会让物品被拿多次,从而违反规则, 但完全背包不用考虑这个问题,

    2024年02月03日
    浏览(58)
  • C++ DP算法,动态规划——背包问题(背包九讲)

    有N件物品和一个容量为 V V V 的背包。放入第i件物品耗费的空间是 C i C_i C i ​ ,得到的价值是 W i W_i W i ​ 。 求解将哪些物品装入背包可使价值总和最大。 这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。 用子问题定义状态:即 F [ i , v ] F[i, v] F

    2024年02月16日
    浏览(51)
  • 【算法宇宙——在故事中学算法】背包dp之完全背包问题

    学习者不灵丝相传,而自杖明月相反,子来此事却无得失。 尽管计算机是门严谨的学科,但正因为严谨,所以要有趣味才能看得下去。在笔者的前几篇算法类文章中,都采用了以小故事作为引入的方式来介绍算法,但在回看的时候发现学术味还是太浓了,完全没有想看下去的

    2023年04月20日
    浏览(53)
  • 【LeetCode动态规划#06】分割等和子集(01背包问题一维写法实战)

    分割等和子集 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。 示例 1: 输入:nums = [1,5,11,5] 输出:true 解释:数组可以分割成 [1, 5, 5] 和 [11] 示例 2: 输入:nums = [1,2,3,5] 输出:false 解释:数组不能分割

    2023年04月09日
    浏览(66)
  • DP算法应用:背包问题解析与实现

    通过详细解析背包问题的动态规划解法,包括状态设计、状态转移方程、两种编码方法(自顶向下和自下而上),以及滚动数组的优化,帮助理解和实现动态规划算法。

    2023年04月08日
    浏览(39)
  • 【LeetCode动态规划#07】01背包问题一维写法(状态压缩)实战,其二(目标和、零一和)

    力扣题目链接(opens new window) 难度:中等 给定一个非负整数数组,a1, a2, ..., an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符号添加在前面。 返回可以使最终数组和为目标数 S 的所有添加符号的方法数。 示例: 输入

    2023年04月18日
    浏览(63)
  • 算法第十五期——动态规划(DP)之各种背包问题

    目录 0、背包问题分类 1、 0/1背包简化版 【代码】 2、0/ 1背包的方案数 【思路】

    2023年04月09日
    浏览(40)
  • 【Java 动态数据统计图】动态数据统计思路案例(动态,排序,动态数组(重点推荐))七(129)

    需求 :前端根据后端的返回数据:画统计图; 说明: 1.X轴为地域,Y轴为地域出现的次数; 2. 动态展示(有地域展示,没有不展示,且高低排序) Demo案例 : 测试输出 : 案例二 : postman接口测试 :

    2024年02月10日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包