动态规划-背包问题详解

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

一、动态规划问题说明

1.题目问题

首先给出背包的容量,接着:

  • 01背包问题:给出每个物品的体积和质量,每个物品最多只能使用一次
  • 完全背包问题:给出每个物品的体积和质量,每个物品可以无限次使用
  • 多重背包问题:给出每个物品的体积、质量和数量,每个物品使用量必须在每个物品给定的数量之类
  • 分组背包问题:给出每个物品的体积、质量和它们的分组,每个组中最多只能取一件物品

在背包的限制之内,做出抉择,选择物品填充背包,使得最终背包的质量最大。

2.Dp解题思路

Dp由于变化较多,没有固定模板,可以从两个方面入手分析,即:状态表示和状态计算,我们把状态设为f[i][j]

  • 状态表示f[i][j]:它表示在前i种物品种选取,使得容量不超过j,满足该情况的所有情况集合,在集合中选取最优解,该最优解的质量即为f[i][j]的值
  • 状态计算:即如何计算f[i][j],每种情况有所不同,且可以优化,优化方式也有所不同,在下面实例分析中进行详细讲解

二、01背包问题

1.问题描述

有 N 件物品和一个容量是 V的背包。每件物品只能使用一次。

第 i件物品的体积是 vi,价值是 wi。

求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。

输入格式

第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。

接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。

输出格式

输出一个整数,表示最大价值。

数据范围

0<N,V≤1000
0<vi,wi≤1000

输入样例
4 5
1 2
2 4
3 4
4 5
输出样例
8

2.朴素算法

  • 我们可以把f[i][j]的状态计算下分,分为对两种情况的取最大值:不包括第i种物品和包括第i种物品
  • 不包括第i种物品:f[i-1][j]
  • 包括第i种物品:f[i-1][j-v[i]]+w[i],即已经含有了第i种物品
代码
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010; //物品的最大数量 

int n,m; //n是物品数量,m是背包的容量
int v[N], w[N]; //v[i]是第i件物品的体积,w[i]是第i件物品的质量
int f[N][N]; //状态表示,全局变量初始化为0 

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 = 0;j <= m;j ++ )
	    {
	    	f[i][j] = f[i - 1][j];
	    	//只有在给定的j容量大于第i个物品的体积时,才可以放第i个物品,不然程序会错误 
	    	if(j >= v[i]) f[i][j] = max(f[i][j],f[i - 1][j - v[i]] + w[i]);
		}
		
	cout << f[n][m] << endl;
	
	return 0;
}

3.优化算法

  • 我们可以把二维f[i][j]化为一维f[j]
  • 状态计算则变为:f[j]=max(f[j],f[j-v[i]]+w[i])
  • 出现问题:如果第二个循环依旧从前往后,则计算f[j]=max(f[j],f[j-v[i]]+w[i])时,已经在第i层中遍历过f[j-v[i]]+w[i],即此时的f[j-v[i]]+w[i]用二维表示为f[i-1][j-v[i]]+w[i],而非f[i][j-v[i]]+w[i],所以第二个循环要从后往前遍历
  • 第二个循环可以再简化:j的最小值遍历到v[i],由于所有f[0~n][j]都存在f[j]中,所以不用遍历小于等于v[i]的部分
代码
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010; //物品的最大数量 

int n,m; //n是物品数量,m是背包的容量
int v[N], w[N]; //v[i]是第i件物品的体积,w[i]是第i件物品的质量
int f[N]; //状态表示,全局变量初始化为0 

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 = m;j >= v[i];j -- )
	    	f[j] = max(f[j],f[j - v[i]] + w[i]);
		
	cout << f[m] << endl;
	
	return 0;
}

三、完全背包问题

1.问题描述

有 N种物品和一个容量是 V的背包,每种物品都有无限件可用。

第 i 种物品的体积是 vi,价值是 wi。

求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。

输入格式

第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。

接下来有 N行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 种物品的体积和价值。

输出格式

输出一个整数,表示最大价值。

数据范围

0<N,V≤1000
0<vi,wi≤1000

输入样例
4 5
1 2
2 4
3 4
4 5
输出样例
10

2.朴素算法

  • 状态计算:我们把f[i][j]分为多种情况取最大值,不取第i个物品,取1个第i个物品,取两个,取三个…,但是满足前提条件是所取的第i物品总质量不大于给定的容量
代码
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010; //物品的最大数量 

int n,m; //n是物品数量,m是背包的容量
int v[N], w[N]; //v[i]是第i件物品的体积,w[i]是第i件物品的质量
int f[N][N]; //状态表示,全局变量初始化为0 

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 = 0;j <= m;j ++ )
	    	for(int k = 0;k * v[i] <= j;k ++ )
	    	f[i][j] = max(f[i][j],f[i-1][j - k * v[i]] + k * w[i]);
	    	//由于k从0开始,所以已经包含了f[i-1][j],不需要单独列出 
		
	cout << f[n][m] << endl;
	
	return 0;
}

3.优化算法

  • f[i][j]=max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2v]+2w,f[i-1][j-3v]+3w,…)
  • f[i][j-v]=max(f[i-1][j-v],f[i-1][j-2v]+w,f[i-1][j-3v]+2w,…)
  • 综上:f[i][j]=max(f[i-1][j],f[i][j-v]+w)
  • 继续优化为一维,不过不用倒置,因为都在第i层
代码
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010; //物品的最大数量 

int n,m; //n是物品数量,m是背包的容量
int v[N], w[N]; //v[i]是第i件物品的体积,w[i]是第i件物品的质量
int f[N]; //状态表示,全局变量初始化为0 

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 ++ )
	    	f[j] = max(f[j],f[j - v[i]] + w[i]);
		
	cout << f[m] << endl;
	
	return 0;
}

四、多重背包问题

1.问题描述

有 N 种物品和一个容量是 V的背包。

第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。

求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。

输入格式

第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。

接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。

输出格式

输出一个整数,表示最大价值。

数据范围

0<N≤1000
0<V≤2000
0<vi,wi,si≤2000

输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例
10

2.朴素算法

  • 在完全背包问题的朴素算法基础上进行
  • 增加一个判断条件:第三个循环多一个k<=s[i]
代码
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010; //物品的最大数量 

int n,m; //n是物品数量,m是背包的容量
int v[N], w[N],s[N]; //v[i]是第i件物品的体积,w[i]是第i件物品的质量,s[i]是第i件物品有多少件
int f[N][N]; //状态表示,全局变量初始化为0 

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 = 0;j <= m;j ++ )
	    	for(int k = 0;k * v[i] <= j && k <= s[i];k ++ )
	    	f[i][j] = max(f[i][j],f[i-1][j - k * v[i]] + k * w[i]);
	    	//由于k从0开始,所以已经包含了f[i-1][j],不需要单独列出 
		
	cout << f[n][m] << endl;
	
	return 0;
}

3.优化算法

  • 利用二进制思想,进行拆包简化
  • 20,21,22,23…2k:可以表示出从0到2k-1其中的所有数
  • 20,21,22,23…2k,C:可以表示出从0到2k+C-1其中的所有数
  • 接着做一遍01背包问题
  • 注意:该题相当于把每个物品拆包为logw个物品,所以开N空间时,开为N*logwmax
代码
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 2500; //物品的最大数量,N+logw 

int n,m; //n是物品数量,m是背包的容量
int v[N], w[N]; //v[i]是第i件物品的体积,w[i]是第i件物品的质量
int f[N]; //状态表示,全局变量初始化为0 

int main()
{
	cin >> n >> m;
	
	int cnt=0;
	
	for(int i = 1;i <= n;i ++ )
	{
		int a,b,s;
		cin >> a >> b >> s;
		int k = 1;
		while(k <= s)
		{
			cnt ++ ;
			v[cnt] = a * k;
			w[cnt] = b * k;
			s -= k;
			k *= 2;
		}
		if(s>0) //防止s刚好用完
		{
			cnt ++;
			v[cnt] = a * s;
			w[cnt] = b * s;
		}
	}
	
	n = cnt; //此时物品相当于有cnt个 
		
	for(int i = 1;i <= n;i ++ )
	    for(int j = m;j >= v[i];j -- )
	    	f[j] = max(f[j],f[j - v[i]] + w[i]);
		
	cout << f[m] << endl;
	
	return 0;
}

五、分组背包问题

1.问题描述

有 N 组物品和一个容量是 V 的背包。

每组物品有若干个,同一组内的物品最多只能选一个。
每件物品的体积是 vij,价值是 wij,其中 i 是组号,j 是组内编号。

求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大。

输出最大价值。

输入格式

第一行有两个整数 N,V,用空格隔开,分别表示物品组数和背包容量。

接下来有 N 组数据:

  • 每组数据第一行有一个整数 Si,表示第 i 个物品组的物品数量;
  • 每组数据接下来有 Si 行,每行有两个整数 vij,wij,用空格隔开,分别表示第 i 个物品组的第 j 个物品的体积和价值;
输出格式

输出一个整数,表示最大价值。

数据范围

0<N,V≤100
0<Si≤100
0<vij,wij≤100

输入样例
3 5
2
1 2
2 4
1
3 4
1
4 5
输出样例
8

2.优化算法

  • 相当于在01背包问题上多了一个分组
  • 分组用一个循环实现,增加第三个循环,遍历每种选择一组中任何一种的情况,取最优解
代码
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 110; //物品的最大数量 

int n,m; //n是物品数量,m是背包的容量
int v[N][N], w[N][N],s[N]; //v[i][j]是第i组第j件物品的体积,w[i][j]是第i组第j件物品的质量,s[i]是第i组有多少个物品 
int f[N]; //状态表示,全局变量初始化为0 

int main()
{
	cin >> n >> m;
	for(int i = 1;i <= n;i ++ )
	{
		cin >> s[i]; //s[i]是第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 >= 0;j -- )
	    	for(int k = 0;k < s[i] && v[i][k] <= j;k ++ )
	    		f[j] = max(f[j],f[j - v[i][k]] + w[i][k]);
		
	cout << f[m] << endl;
	
	return 0;
}

六、总结

从上例我们可以看到,01背包问题、多重背包问题、分组背包问题其实十分相似,多重背包优化是进行二进制操作拆包后的01背包优化,分组背包优化是多了一个循环的01背包优化,第二个循环都需要倒置。而完全背包问题相较于01背包问题优化,唯一的区别在于第二个循环是否倒置。文章来源地址https://www.toymoban.com/news/detail-821878.html

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

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

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

相关文章

  • 动态规划-----背包类问题(0-1背包与完全背包)详解

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

    2024年04月17日
    浏览(35)
  • 【算法-动态规划】0-1 背包问题

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月08日
    浏览(47)
  • 算法学习17-动态规划01:背包问题

    提示:以下是本篇文章正文内容: 提示:这里对文章进行总结: 💕💕💕

    2024年04月27日
    浏览(53)
  • 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)
  • 【动态规划】01背包问题——算法设计与分析

    若超市允许顾客使用一个体积大小为13的背包,选择一件或多件商品带走,则如何选择可以使得收益最高? 商品 价格 体积 啤酒 24 10 汽水 2 3 饼干 9 4 面包 10 5 牛奶 9 4 0-1 Knapsack Problem 输入: quad - n n n 个商品组成集合 O O O ,每个商品有属性价格 p i p_i p i ​ 和体积 v i v_i v

    2024年02月04日
    浏览(79)
  • acwing算法基础之动态规划--背包问题

    (零) 背包问题描述:有 N N N 个物品,每个物品的体积是 v i v_i v i ​ ,价值是 w i w_i w i ​ ,现有容量是 V V V 的背包,求这个背包能装下的物品的最大价值。 01背包问题:每个物品只有1个。 完全背包问题:每个物品有无穷多个。 多重背包问题:第 i i i 个物品有 s i s_i s

    2024年02月05日
    浏览(47)
  • 贪心算法解决背包问题和动态规划解决0-1背包问题(c语言)

    运行结果如下: 运行结果如下: 总结: 贪心算法: 每一步都做出当时看起来最佳的选择,也就是说,它总是做出局部最优的选择。 贪心算法的设计步骤: 对其作出一个选择后,只剩下一个子问题需要求解。 证明做出贪心选择后,原问题总是存在最优解,即贪心选择总是安

    2024年02月04日
    浏览(56)
  • 算法套路十四——动态规划之背包问题:01背包、完全背包及各种变形

    如果对递归、记忆化搜索及动态规划的概念与关系不太理解,可以前往阅读算法套路十三——动态规划DP入门 背包DP介绍:https://oi-wiki.org/dp/knapsack/ 0-1背包:有n个物品,第i个物品的体积为w[i],价值为v[i],每个物品至多选一个, 求体积和不超过capacity时的最大价值和,其中i从

    2024年02月10日
    浏览(60)
  • 【Java实现】动态规划算法解决01背包问题

    1、问题描述: 一个旅行者有一个最多能装m公斤的背包,现在有n中物品,每件的重量分别是W1、W2、……、Wn,每件物品的价值分别为C1、C2、……、Cn, 需要将物品放入背包中,要怎么样放才能保证背包中物品的总价值最大? 2、动态规划算法的概述 1)动态规划(Dynamic Progra

    2023年04月09日
    浏览(57)
  • 动态规划:完全背包问题----中专生刷算法

    需要基础:闫氏dp分析法,01背包问题 先去看一下01背包问题,再看完全背包 动态规划:选择dp及优化01背包问题-CSDN博客 做过01背包问题的同学会发现,完全背包问题的代码 在01背包基础上改动很小,但是里面的思想,有很大差距 题目 有 N 种物品和一个容量是 V的背包,每种物品

    2024年04月16日
    浏览(48)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包