legend

前言：我们这里的背包问题与完全背包问题的最大不同点是可否重复投放相同的物品，而我们这里完全背包问题解除了这个限制，所以我们要对背包问题进行进一步的改进，从而完成问题，背包问题我也写了题解，感兴趣的可以去看看
		相同点：背包问题与完全背包问题相同点在于都运用一个备忘录来保存我们投放的情况，然后从备忘录中筛选我们的最优解。
		不同点：在于我们对于最后比较的时候背包问题是时刻与前一次做比较，即是否加入本次的物品，比如我们的关键代码（背包问题）
		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 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

　　评论区

守恒

"为什么后面的i-1改成i，就可以完成任务呢，因为在每一次max比较的时候，比较的是不加入本次物品的价值与加入本次物品的价值，但是这里的本次是你每一次背包容量都扩大的情况下都可以选择是否加入本次物品，而背包问题是上一次加本次，完全背包问题是是否本次加本次的物品。"
这句写得好,简单易懂

2023-01-09 20:11:49

legend

TA的其他文章

你可能喜欢

母牛的故事（C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

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

评论区

精彩推荐

川哥的吩咐（C++代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

【绝对值排序】（C语言代码）

校门外的树（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

K-进制数（C语言描述，蓝桥杯）

legend

TA的其他文章

你可能喜欢

母牛的故事 （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

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

评论区

精彩推荐

川哥的吩咐 （C++代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C语言训练-求矩阵的两对角线上的元素之和 （C语言代码）

【绝对值排序】 （C语言代码）

校门外的树 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

K-进制数 （C语言描述，蓝桥杯）

母牛的故事（C语言代码）

　　评论区

川哥的吩咐（C++代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

【绝对值排序】（C语言代码）

校门外的树（C语言代码）

K-进制数（C语言描述，蓝桥杯）