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语言代码）怎么答案错误？？？？？

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

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

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

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

评论区

精彩推荐

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

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

本人酷爱递归实现很多问题，这里也是

WU-判定字符位置（C++代码）

剪刀石头布（C语言代码）

P1000 （C语言代码）

1054题解

1051（奇了怪了）

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

蓝桥杯历届试题-翻硬币（C++代码）

legend

TA的其他文章

你可能喜欢

回文数字 （C++代码）

汽水瓶 （C语言代码）怎么答案错误？？？？？

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

C语言训练-求1+2!+3!+...+N!的和 （C语言代码）

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

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

评论区

精彩推荐

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

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

本人酷爱递归实现很多问题，这里也是

WU-判定字符位置 （C++代码）

剪刀石头布 （C语言代码）

P1000 （C语言代码）

1054题解

1051（奇了怪了）

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

蓝桥杯历届试题-翻硬币 （C++代码）

回文数字（C++代码）

汽水瓶（C语言代码）怎么答案错误？？？？？

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

　　评论区

WU-判定字符位置（C++代码）

剪刀石头布（C语言代码）

蓝桥杯历届试题-翻硬币（C++代码）