01背包—动态规划

这篇具有很好参考价值的文章主要介绍了01背包—动态规划。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、背包问题概述:

01背包—动态规划

二、暴力解法:

重量 价值
物品0 1 15
物品1 3 20
物品2 4 30

背包最大容量为4。

每一个物品有两个状态,“取”或者“不取”。利用回溯法可以暴力枚举所有物品的状态的排列组合状态,与背包最大容量比较就可以求得最大的价值,时间复杂是 O ( 2 n ) O(2^n) O(2n)为指数级别,故需要动态规划的解法来进行优化。

三、二维DP数组解01背包

1.DP数组含义

dp[i][j]:任取编号为[0,i]内的物品,放到容量为j的背包内所得到的最大价值。

2.递推公式(对dp[i][j])

  1. 不放物品idp[i][j]=dp[i-1][j]
  2. 放物品idp[i][j]=dp[i-1][j-weight[i]] + value[i]

dp[i][j]最终应该取放物品i和不放物品i中大的那一个值。

故,dp[i][j]=max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])

3.DP数组解析

01背包—动态规划
如图,对于dp[i][j](红色表格),其取值由两个方向得到:

  1. dp[i][j]=dp[i-1][j],由1号红色箭头得到;
  2. dp[i][j]=dp[i-1][j-weight[i]] + value[i],由2号箭头得到。具体2号箭头的初始位置则由weight[i]决定。

所以,求解DP数组时[i-1]必须是已知的,故DP数组初始化时第一行必须初始化。

第一列不需要初始化,使用if判断j-weight[i] > 0 即可。

综上,初始化时,只初始化第一行,其余位置皆不用初始化。

就本题而言,初始化数组为:
01背包—动态规划

4.遍历顺序

i先遍历物品再遍历背包

01背包—动态规划
本方法本质是按行遍历,对每个物品从容量0j逐个测试。由DP数组解析可得,求dp[i][j]时必须知道dp[i-1][0~j]内的所有数据,而这在前一次循环中已经得到。故该遍历方法可行。

ii先遍历背包再遍历物品

01背包—动态规划 本方法本质是按列遍历,对每个容量从物品0i逐个测试。由DP数组解析可得,求dp[i][j]时必须知道dp[i-1][0~j]内的所有数据,而这在前一次循环中已经得到。故该遍历方法可行。

5. 代码:

void knapsack () {
    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];
    }
    // 先遍历物品
    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]);
        }
    }
    // 先遍历背包
    // for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
    //    for(int 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 << dp[weight.size() - 1][bagweight] << endl;
}

四、一维DP数组(滚动数组)解01背包

1.DP数组含义

从二维DP数组的遍历图中可以看出求解dp[i][j]完全是在使用DP数组的前一行(或前一列)的数据,且对dp[i][j]后面的内容完全不关心。因此,可以考虑将前一行(或前一列)的数据覆盖到当前行,使用一行(或一列)就可以完成计算,这就是本题一维DP数组的思想。

本题定义dp[j]为容量为j的背包能装物品的最大价值(相当于将二维数组压缩为一行)。

2.递推公式

  1. 不放物品idp[j]=dp[j](可以将等号后dp[j]的看作上一行的数据,只是覆盖到了当前行)
  2. 放物品idp[j]=dp[j-weight[i]]+value[i](可以将等号后的dp[j-weight[i]]看作上一行的数据,只是覆盖到了当前行)

dp[j]=max(dp[j], dp[j-weight[i]]+value[i])

3.DP数组初始化

由数组的定义可知,求dp[j]只需知道其前面的数据即可。考虑一下,最“前面”的数据就是背包不放任何物体。故将DP数组所有元素设置为0即可。

4.遍历顺序

因为当前DP数组的值可以看成为上一行的覆盖,故为了保持dp[j]前的元素的“干净”,遍历j时应该采用倒叙遍历。
01背包—动态规划
如图,蓝色代表当前行已经更新的值,红色代表当前行正要求的值,绿色代表上一行还没有更新的值。从后往前遍历可以保证对dp[j]更新时,其前面的值都不会被改变。如果采用正序遍历,相当于dp[j]前的值为当前行的值(这种说法也不对,物品i的值被累加了),递推公式就不成立了。

假设物品重量{1, 1},价值{5, 10},背包最大容量为4。如图,若采用正序遍历
01背包—动态规划
在第二行更新DP时,由于dp[j]前的数据已经被污染,故每次更新dp[j]时都对物品1的价值进行了累加。而倒叙时由于前面数据没有被污染,则不会产生累加的错误。如图:
01背包—动态规划文章来源地址https://www.toymoban.com/news/detail-457802.html

5.代码

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 << dp[bagWeight] << endl;
}

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

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

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

相关文章

  • 动态规划——01背包问题

    由于本人实力尚浅,接触算法没多久,写这篇blog仅仅是想要提升自己对算法的理解,如果各位读者发现什么错误,恳请指正,希望和大家一起进步。(●’◡’●) 状态表示 :用一个数组 f[][] (数组可能是一维也可能是二维,根据具体题目具体分析)来表示某个集合,这个集合

    2024年02月03日
    浏览(43)
  • 动态规划:01背包问题(二)

    上篇博客动态规划:01背包问题(一)将的是用二维数组来解决,而本篇博客就是把二维dp数组降为一维dp数组(滚动数组)在使用二维数组的时候,递推公式:dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 其实可以发现如果 把dp[i - 1]那一层拷贝到dp[i]上 ,表达式完全可以是

    2024年01月22日
    浏览(58)
  • 动态规划(01背包问题)

    本文默认读者具有动态规划前置知识 动态规划的特点: 重叠子问题 状态转移方程 最优子结构 题型: 求最值 解题套路: 明确【状态】 明确【选择】 明确dp函数/数据的定义 明确base case 例:给你一个可装载容量为W的背包和N个物品,每个物品有重量和价值两个属性。其中第

    2024年04月16日
    浏览(37)
  • 动态规划01背包问题

    假设你是一名经验丰富的探险家,背着背包来到野外进行日常探险。天气晴朗而不燥热,山间的风夹杂着花香,正当你欣赏这世外桃源般的美景时,突然,你发现了一个洞穴,这个洞穴外表看起来其貌不扬,但凭借着惊为天人的直觉,这个洞穴不简单。于是,你开始往洞穴内

    2024年02月06日
    浏览(41)
  • 动态规划_01背包问题

    描述 一个旅行者有一个最多能装   M   公斤的背包,现在有   n   件物品,它们的重量分别是   W 1 ​ , W 2 ​ , ... , W n ​ , 它们的价值分别为   C 1 ​ , C 2 ​ , ... , C n ​ ,求旅行者能获得最大总价值。 输入描述 第 1 行:两个整数, M   (背包容量, M ≤ 200   )和   N  

    2024年04月29日
    浏览(39)
  • 动态规划-01背包问题

    算法思路: 背包问题的状态表⽰⾮常经典,如果⼤家不知道怎么来的,就把它当成⼀个「模板」记住吧~ 我们先解决第⼀问: 1. 状态表⽰ : dp[i][j] 表⽰:从前 i 个物品中挑选,总体积「不超过」 j ,所有的选法中,能挑选出来 的最⼤价值。 2. 状态转移⽅程 : 线性 dp 状态

    2024年04月11日
    浏览(42)
  • 算法系列--动态规划--背包问题(1)--01背包介绍

    💕\\\"趁着年轻,做一些比较cool的事情\\\"💕 作者:Lvzi 文章主要内容:算法系列–动态规划–背包问题(1)–01背包介绍 大家好,今天为大家带来的是 算法系列--动态规划--背包问题(1)--01背包介绍 背包问题是动态规划中经典的一类问题,经常在笔试面试中出现,是非常 具有区分度 的题

    2024年04月16日
    浏览(52)
  • 动态规划母题:01背包问题

    动态规划与图论,前缀和与差分等有模板的算法不同,动态规划更考察思维能力,而不是运用模板的能力。 个人认为 Acwing 关于动态规划的讲解比较容易理解。我会根据 Acwing 的动态规划解题思路来讲解题目。 虽说动态规划没有固定的模板,但是还是有相对固定的套路。但

    2024年02月12日
    浏览(62)
  • C++ 动态规划 01背包问题

    有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi ,价值是 wi 。 求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。 输出最大价值。 输入格式 第一行两个整数, N,V ,用空格隔开,分别表示物品数量和背

    2024年04月27日
    浏览(39)
  • 动态规划-01背包问题(python)

    对于动态规划问题,就是牺牲空间来提高时间,通过将一个个小问题的答案存储起来,直接供给后面问题求解,避免重复的运算,从而提高效率,这就是动态规划的思想。 下面我们通过一个经典的01背包问题来了解动态规划的解题方法吧(文末附上完整代码) 首先,将每个物

    2024年02月06日
    浏览(43)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包