完全背包问题（动态规划，超级详细，保证教会，同时与背包问题做对比）

255 阅读 1 评论 0 点赞

前言：我们这里的背包问题与完全背包问题的最大不同点是可否重复投放相同的物品，而我们这里完全背包问题解除了这个限制，所以我们要对背包问题进行进一步的改进，从而完成问题，背包问题我也写了题解，感兴趣的可以去看看
		相同点：背包问题与完全背包问题相同点在于都运用一个备忘录来保存我们投放的情况，然后从备忘录中筛选我们的最优解。
		不同点：在于我们对于最后比较的时候背包问题是时刻与前一次做比较，即是否加入本次的物品，比如我们的关键代码（背包问题）
		c[i][j]=max(c[i-1][j],c[i-1][j-a[i]]+b[i])。
		这里解释一下c[i-1][j-a[i]]+b[i])，首先就是考虑是否加入第i个物品，如果我要加入这个物品，那么我们是不是要给背包腾出位置？，要腾出来正好能容下这个物品的空间，所以就是j-a[i]，当然你放进去的话是不是要加上他的价值？所以加上b[i],那么肯定有人问了，那你拿出一个物品不是要减去拿出的物品的价值？哈哈，其实我们的备忘录其实已经帮我们解决了。
		如i=4，j=10，a[i]=3,[3][10]与c[3][10-3]+b[3]，那我们c[3[10-3]的数据是不是前面我们已经做过了？所以我们这里是已经直接处理过的，直接用就可以了。
		以上就是背包问题的思路。那么其实解决了背包问题，完全背包问题其实也接近解决了，只需要改一关键代码为
		c[i][j]=max(c[i-1][j],c[i][j-a[i]]+b[i])。
		为什么后面的i-1改成i，就可以完成任务呢，因为在每一次max比较的时候，比较的是不加入本次物品的价值与加入本次物品的价值，但是这里的本次是你每一次背包容量都扩大的情况下都可以选择是否加入本次物品，而背包问题是上一次加本次，完全背包问题是是否本次加本次的物品。
		话不多说，看代码：
		
	#include<stdio.h>
	int max(int e,int f);  //这里为比较函数
	int main()
	{   //注意注意c[i][j]中i是可选择的物品数，不是装下的物品数，j为背包容量，通过i=1,j=1开始遍历，记录不同容量下装入不同情况物品时的价值
		int a[31],b[201],c[31][201]={0}; //记得要初始化数组
		int n,m;
		int i,j;
		scanf("%d%d",&m,&n);
		for(i=1;i<=n;i++)
		{
			scanf("%d%d",&a[i],&b[i]);
		}
		for(i=1;i<=n;i++)  //先从一个物品开始，
		{
			for(j=1;j<=m;j++)  //每次背包容量逐渐增大，也就是从背包容量为1~10装下不同物品的情况
			
			{
				if(a[i]>j) //如果装不下
				{
					c[i][j]=c[i-1][j];
				}
					else //如果装的下，就要讨论要不要装，因为装了不一定价值大
					{  //此处为核心代码
						c[i][j]=max(c[i-1][j],c[i][j-a[i]]+b[i]);
					}
			}
		}
		printf("max=%d",c[n][m]);    //输出最终结果
	}
	int max(int e,int f)    //这里我们也可以使用三木运算符。（看个人）
	{
		int c;
		if(e>f)
		c=e;
		if(e<f)
		c=f;
		return c;
	}

0.0分

3 人评分

本文分类：题解列表
浏览次数：255 次浏览
发布日期：2022-12-18 17:37:27
本文链接：https://blog.dotcpp.com/a/92270

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

完全背包问题（动态规划，超级详细，保证教会，同时与背包问题做对比）

评论列表共有 1 条评论

发表评论取消回复

完全背包问题（动态规划，超级详细，保证教会，同时与背包问题做对比）

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 1 条评论

发表评论 取消回复

评论列表共有 1 条评论

发表评论取消回复