【动态规划】背包问题题型及方法归纳

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

背包问题的种类

背包问题是在规定背包容量为j的前提下,每个物品对应的体积为v[i],价值为w[i],从物品0到物品i中选择物品放入背包中,找出符合某种要求的价值

(1)背包问题种类

  • 01背包:每种物品只能选择1个。
  • 完全背包:每种物品可以选择无限个。
  • 多重背包:每种物品最多可选s[i]个。
  • 分组背包:有若干个组,每组内有若干个物品,每个物品只能选一次。

(2)递推公式

  • 01背包:dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i])
  • 完全背包:dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i])
  • 多重背包:dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i], dp[i - 1][j - 2 * v[i]] + w[i] + ... + dp[i - 1][j - s[i] * v[i]] + s[i] * w[i])
  • 分组背包:dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i][k] + w[i][k], + ... + dp[i - 1][j - s[i]*v[i][k]] + s[i] * w[i][k])

(3)滚动数组遍历顺序:
遵循原则:用到上一层的信息i-1,则从大到小遍历;用到本层的信息i,则从小到大遍历。

  • 01背包:从大到小
  • 完全背包:从小到大。组合问题:先物品,再背包。排列问题:先背包,再物品。
  • 多重背包:在01背包的基础上,用到i-1层信息,从大到小,多一层for循环选物品个数
  • 分组背包:在01背包的基础上,用到i-1层信息,从大到小,多一层for循环选物品个数

(4)初始化问题:

  • 要求恰好装满:dp[i][0] = 0, dp[j] = -∞ (j ≠ 0)
  • 要求恰好装满:dp[i][0] = dp[j] = 0

可以这样理解:初始化的dp数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满,那么此时只有容量为0的背包可以在什么也不装且价值为0的情况下被“恰好装满”,其它容量的背包均没有合法的解,属于未定义的状态,应该被赋值为-∞了。如果背包并非必须被装满,那么任何容量的背包都有一个合法解“什么都不装”,这个解的价值为0,所以初始时状态的值也就全部为0了。

(5)题型特点

  • 01背包:已给数组中可用元素固定且每次只能用一次,限制容量固定(可能会存在多重背包容量)。

1、01背包问题

主要分为两部分:状态表示状态计算

1. 状态表示dp[i][j]
i是物品个数,j是条件限制。状态表示一般从两个角度考虑,分别为集合属性
其中,集合是只考虑前i个物品,不超过j的选法集合。属性值的是数量最大值最小值等。当要求的数到达某一个值时,就要求j - v[i]到达那个相应的值时,会更新,这就要求设置好初始值,一般会让dp[i][0]=0dp[i][0]=1

2. 状态计算
状态计算主要是集合划分,分为 f(i-1, j) 所有不选第i个物品的方案所有选择第i个物品的方案,这种方式可保证不遗漏和不重复

(1)不超过j的条件下,对于所有不选第i个物品的方案
因为是对i从0开始按顺序遍历,因此选择的是从0-i-1中的选择方案。

(2)不超过j的条件下,所有选择第i个物品的方案
此集合包含两个部分,一个是含有第i个物品,另一个是不含第i个物品从0-i-1中选择的方案。含有第i个物品时,表示的是物品i的体积v[i]为唯一的定量不含第i个物品时,条件就变为j - v[i],减去了第i个物品的体积,在此条件下,从0-i-1中选,此时会有多种方案,为变量。按我们的目标要求,如果要找最大值,就从多种方案中的一个最大值方案,如果要找最小值,就从多种方案中的最小值方案。两个部分相加,就是我们此方案的结果

背包问题,数据结构与算法刷题,# 动态规划,动态规划,算法,图论
dp[i][j]二维数组

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;
int dp[N][N];

int main(){

    int n, m;
    int v[N], w[N];
    
    cin >> n >> m;
    for(int i = 1; i <= n; i++)         cin >> v[i] >> w[i];
    
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            // 当前物品重量大于背包容量时,不放该物品
            if(j < v[i])        dp[i][j] = dp[i - 1][j];
            // 当前物品重量小于等于背包容量时,在放该物品后和不放该物品之间选择一个最大价值
            else                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
        }
    }
    
    cout << dp[n][m] << endl;
    
    return 0;
}

dp[j]一维滚动数组
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i])改为等价式dp[j] = max(dp[j], dp[j - v[i]] + w[i]),遍历顺序改变为从大到小,通常会初始化dp[0]=0dp[o]=1

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;
int dp[N];

int main(){

    int n, m;
    int v[N], w[N];
    
    cin >> n >> m;
    for(int i = 1; i <= n; i++)         cin >> v[i] >> w[i];
    
    for(int i = 1; i <= n; i++) {
        // 从后向前遍历,表示装入一个物品后,剩余的可装入容量达到的最大价值
        for(int j = m; j >= v[i]; j--) {
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    
    cout << dp[m] << endl;
    
    
    return 0;
}

151、【动态规划】leetcode ——2. 01背包问题(C++版本):二维数组+滚动数组

拓展应用:

  1. 152、【动态规划】leetcode ——416. 分割等和子集:滚动数组+二维数组(C++版本):将重量之和除以2,作为背包容量,找到能让背包中可装物体体积最大的装发,让背包中装入物品的重量等于背包容量。

  2. 【动态规划】leetcode ——1049. 最后一块石头的重量 II:滚动数组(C++版本):思路与上一题相同,分割成两个数量相近的集合,最后两个集合的综合相减。

  3. 154、【动态规划】leetcode ——494. 目标和:回溯法+动态规划(C++版本):分割成正数集合和负数集合,背包容量为正数集合大小,找到可组成正数集合大小的组合方式。

  4. 155、【动态规划】leetcode ——474. 一和零:三维数组+二维滚动数组(C++版本):字符串作为物品,m个0和n个1作为背包容量(具有多重背包)。

2、完全背包问题

与01背包的区别在于同一个物品可以有无限个,对同一个物品可选择多次。

背包问题,数据结构与算法刷题,# 动态规划,动态规划,算法,图论

状态计算时,在dp[i][j]情况下 ,划分集合时01背包只能 划分成两个集合 ,而完全背包可以划分为多个集合(第i个物品选择0个、1个、2个…一直到体积达到或超过j为止的多种方案),其中选择0个时,就相当于在0-i-1中选择的方案dp[i - 1][j]。

递推公式表达式为:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i], dp[i - 1][j - 2*v[i]] + 2*w[i] + ... + dp[i - 1][j - n*v[i]] + n*w[i])(n*v[i]刚好小于等于j)

现在来进行简化,由上式可知,dp[i][j - v[i]] = max(dp[i - 1][j - v[i]], dp[i - 1][j - 2*v[i]] + w[i] + ... + dp[i - 1][j - n*v[i]] + (n-1)*w[i]),对该式两端加上一个w再联立第一个式子,从而得最终简化式子:

dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i])

dp[i][j]二维数组

#include <iostream>

using namespace std;

const int N = 1010;
int dp[N][N];
int v[N], w[N];
int n, m;

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++)      cin >> v[i] >> w[i];
    
    for(int i = 1; i <= n; i++) {
        for(int j = 1;j <= m; j++) {
            if(v[i] > j)        dp[i][j] = dp[i - 1][j];
            else                dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i]);
        }
    }
    
    cout << dp[n][m] << endl;
    
    return 0;
}

d[j]一维滚动数组
滚动数组的遍历顺序按照从小到大遍历。

#include <iostream>

using namespace std;

const int N = 1010;
int dp[N];
int v[N], w[N];
int n, m;


int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++)      cin >> v[i] >> w[i];
    
    for(int i = 1; i <= n; i++) {
        for(int j = v[i]; j <= m; j++) {
            // dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i])
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    
    cout << dp[m] << endl;
    
    return 0;
    
}

156、【动态规划】AcWing ——3. 完全背包问题:二维数组+一维滚动数组(C++版本)

拓展应用:
完全背包中,会牵扯两个不同的问题:组合问题和排列问题。对于组合问题,就是规定一批相同的元素,不同的排列代表同一个结果。而排列问题,就是规定一批相同的元素,不同的排列代表不同的结果。为了实现这两个问题,通常会让组合问题遍历顺序是先遍历物品,再遍历背包,这样子可以让dp只记录某一结果中的一种情形仅被记录。而排列问题遍历顺序是先遍历背包,再遍历物品,这样子可以让dp记录所有的排列出现的情况

例如,[1, 3]和[3, 1],在组合问题中只记录了[1, 3]这种情况即可。而在排列问题中,[1, 3]和[3, 1]都被记录了下来。
先遍历物品,再遍历背包,会让某一物品,在各个容量的情况下按物品放入顺序被唯一确定下来放还是不放。
先遍历背包,再遍历物品,会让在不同容量下,都将各个物品从头遍历了一遍,就会得到所有的排列情况。

无顺序要求的题目:

  1. 159、【动态规划】leetcode ——322. 零钱兑换:二维数组+一维滚动数组(C++版本):注意求最小值的初始化,由于不考虑顺序问题,因此遍历顺序都可以,dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i]])。

  2. 160、【动态规划】leetcode ——279. 完全平方数:二维数组+一维滚动数组(C++版本):方式同上,递推公式用上完全平方数形式,dp[i][j] = min(dp[i - 1][j], dp[i][j - i * i] + 1)。

(1)组合问题

数组中元素相同、顺序不同视为同一个结果,组合问题遍历顺序按先物品,再遍历背包。

  1. 158、【动态规划】leetcode ——518. 零钱兑换 II:二维数组+一维滚动数组(C++版本):零钱可以多次使用不考虑数字顺序位置关系,累加计算dp[i][j] = dp[i - 1][j] + dp[i][j - v[i]]。

  2. 191、【动态规划】AcWing ——AcWing 900. 整数划分:完全背包解法+加减1解法(C++版本):dp[i][j] = (dp[i - 1][j] + dp[i][j - i]),从1~n中选数,组合成总额和为j的方案个数。

(2)排列问题

数组中元素相同、顺序不同视为不同结果,排列问题遍历顺序按先背包,再遍历物品。最内层再加上一个从0-i再遍历探寻各种情况的for循环。

  1. 158、【动态规划】leetcode ——377. 组合总和 Ⅳ(C++版本):数字可以多次使用考虑数字顺序位置关系,一维滚动数组累加计算dp[j] += dp[j - v[i]],二维比较特别sum(dp[i][j], dp[i][j - nums[k]),内层需要从0-i再遍历一次。

  2. 145、【动态规划】leetcode ——70. 爬楼梯:暴力法+动态规划(C++版本):完全背包解法与题2相同,也是排列问题。

  3. 161、【动态规划】leetcode ——139. 单词拆分:回溯法+动态规划(C++版本):这个题比较奇特一些,当满足前面的字符可以被组成并且当前单词可以有字典中组成时,为dp[j] = true

3、多重背包问题

多重背包是对每种物品的数量进行限制,dp[i][j]的意思:在第i种物品的个数为规定s[i]个的前提下,背包容量为j,物品体积为v[i],从物品0到物品i中选择物品,可达到的最大价值。

实现方式是在01背包实现的基础上,遍历时候,在最内层设置一个for循环,寻找从一个都不选到选s[i]个第i个物品时,哪种情况取得最大价值。

dp[i][j]二维数组

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int dp[N][N];
int v[N], w[N], s[N];


int main() {
    cin >> n >> m;
    
    for(int i = 1; i <= n; i++)         cin >> v[i] >> w[i] >> s[i];
    
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            // 一个都不选一直到选s[i]个,选择一种最大价值情况
            for(int k = 1; k <= s[i] && j >= k * v[i] ; k++) {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - k * v[i]] + k * w[i]);
            }
        }
    }
    
    cout << dp[n][m] << endl;
    
    return 0;
    
}

d[j]一维滚动数组

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int dp[N];
int v[N], w[N], s[N];


int main() {
    cin >> n >> m;
    
    for(int i = 1; i <= n; i++)         cin >> v[i] >> w[i] >> s[i];
    dp[0] = 0;
    
    for(int i = 1; i <= n; i++) {
        for(int j = m; j >= 0; j--) {
            // 一个都不选一直到选s[i]个,选择一种最大价值情况
            for(int k = 0; k <= s[i] && j >= k * v[i] ; k++) {
                dp[j] = max(dp[j], dp[j - k * v[i]] + k * w[i]);
            }
        }
    }
    
    cout << dp[m] << endl;
    
    return 0;
    
}

162、【动态规划】AcWing ——4. 多重背包问题 I(C++版本)

4、分组背包

分组背包问题是在01背包的基础上,多了一个组的概念。有若干个组,每组里面有若干个物品,每个物品只能选择一次,找到在背包容量为j的前提下,从0-i组中选择物品,达到背包里价值最大。

d[j]一维滚动数组

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;
int n, m;
int v[N][N], w[N][N], s[N];
int dp[N];
                    
int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> s[i];
        for(int j = 0; j < s[i]; j++) {
            cin >> v[i][j] >> w[i][j];
        }
    }
    
    for(int i = 1; i <= n; i++) {                   // 遍历物品
        for(int j = m; j >= 1; j--) {               // 从大到小,遍历背包(使用i-1层信息)
            for(int k = 0; k < s[i]; k++) {         // 遍历每组内的物品个数
                if(j >= v[i][k]) {
                    dp[j] = max(dp[j], dp[j - v[i][k]] + w[i][k]);
                }
            }
        }
    }
    
    cout << dp[m] << endl;
    
    
    
    return 0;
}

166、【动态规划】AcWing ——9. 分组背包问题(C++版本)文章来源地址https://www.toymoban.com/news/detail-782040.html

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

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

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

相关文章

  • 【动态规划专栏】-- 回文串问题 -- 动态规划经典题型

    目录 动态规划 动态规划思维(基础) 状态表示(最重要) 状态转移方程(最难) 初始化(细节) 填表顺序(细节) 返回值(结果) 回文子串 ⭐⭐ 【题目解析】  【算法原理】 C++ 算法代码  最长回文子串 ⭐⭐  【题目解析】  【算法原理】 C++ 算法代码   回文串分割

    2024年02月08日
    浏览(46)
  • 0-1背包问题(Knapsack Problem)-动态规划方法(C语言递归和迭代)

    前言 背包0-1问题属于典型的求最大/最小子集问题范畴,它不像rod-cutting或matrix-chain-multiplication等问题,求解过程是按照单位等增或单位递减,0-1背包问题属于在集合范围内的某一个值,而且这些值大概率不是连续值。 问题描述 假定有N件物品,每件物品具有特定的价值value

    2024年02月06日
    浏览(44)
  • Java数据结构与算法----动态规划(背包篇)

    1.1.算法思路 0/1背包是动态规划、背包问题中最经典的问题啦!它主要的问题是: 给定n种物品、这n种物品的重量分别是,价值分别是 ,而你有一个容量为C的背包,请问如何求出所能拿的最大价值呢? 对于动态规划,我们先需要找到一条推导公式,然后确定边界: 我们设

    2024年02月07日
    浏览(50)
  • 动态规划-背包问题-完全背包

    对比01背包,完全背包中的每件物品有无数件。 也就是说,每件物品可以拿0,1,…,k,…件。 dp[i][j]表示前i种物品,体积为j时的最大价值 对于第i件物品: 不拿:dp[i][j]⇐dp[i-1][j] 拿一件:dp[i][j]⇐dp[i-1][j-w[i]]+v[i] 拿两件:dp[i][j]⇐dp[i-1][j-2w[i]]+2v[i] … 拿k件:dp[i]][j]⇐dp[i

    2024年04月08日
    浏览(49)
  • 动态规划之背包问题——完全背包

    算法相关数据结构总结: 序号 数据结构 文章 1 动态规划 动态规划之背包问题——01背包 动态规划之背包问题——完全背包 动态规划之打家劫舍系列问题 动态规划之股票买卖系列问题 动态规划之子序列问题 算法(Java)——动态规划 2 数组 算法分析之数组问题 3 链表 算法

    2024年02月03日
    浏览(64)
  • 完全背包&多重背包问题(动态规划)

    完全背包问题: 每个物品使用次数没有限制,与0-1背包的不同之处在于 遍历背包的顺序 是正序。 多重背包问题: 与完全背包的区别在于,每一种物品是有个数限制的,不能无限选择。这篇博客讲解的非常详细,可以参考学习: 多重背包问题---超详细讲解+优化(不懂你揍我

    2024年04月10日
    浏览(48)
  • 动态规划DP之背包问题3---多重背包问题

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

    2024年03月20日
    浏览(49)
  • 动态规划-----背包类问题(0-1背包与完全背包)详解

    目录 什么是背包问题? 动态规划问题的一般解决办法: 0-1背包问题: 0 - 1背包类问题  分割等和子集:  完全背包问题:  完全背包类问题 零钱兑换II: 背包问题(Knapsack problem)是一种组合优化的NP完全问题。 问题可以描述为:给定一组物品,每种物品都有自己的重量和价格

    2024年04月17日
    浏览(35)
  • 算法系列--动态规划--背包问题(3)--完全背包介绍

    💕\\\"Su7\\\"💕 作者:Lvzi 文章主要内容:算法系列–动态规划–背包问题(3)–完全背包介绍 大家好,今天为大家带来的是 算法系列--动态规划--背包问题(3)--完全背包介绍 链接: 完全背包 可以发现完全背包问题和01背包问题还是特比相似的 分析: 完全背包问题 是 01背包问题 的推广

    2024年04月25日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包