legend

动态规划问题是算法的一大难题，但是他的思想其实就是保存所有情况，在所有情况中找到解，我们可以创建一个”备忘录“，把每一个情况写到这个备忘录中，直到所有的情况都写到我们的备忘录的时候，找到我们满意的解答。
		注意我们要创建我们的”备忘录“，这里我们创建备忘录c[i][j]。i表示他的装东西可选择的个数，注意注意注意是可选择的个数，而不是放下的个数，j表示他的容量大小。
		
		疑问一：max(c[i-1][j],c[i-1][j-a[i]]+b[i])这个代码是什么意思？
		答：就是要看要不要装下这个物品，前者是不装入本物品，后者是要装本物品，但是条件是要从里面腾出正好够他装的位置，所以这就是为什么j-a[i]的原因，当然你既然装入了，那么价值就要加上他的价值b[i]；同时再解释一下c[i-1][j-a[i]]，这个假如i=4,j=7,a[i]=3，那么就是c[3][3]，c[3][3]的最好情况我们已经保存到备忘录了，直接用就行了。
		
		疑问二：为什么是i-1？
		答：因为i-1表示前i个物品的总价值。
	#include<stdio.h>
	int max(int e,int f);
	int main()
	{     //这里a数组用来保存我们的每一个东西的重量，b数组来保存价值大小
		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++)    //我们的背包容量依次增加
			{
				if(a[i]>j) //这里是物品的重量大于我们的背包重量，即放不下
				{
					c[i][j]=c[i-1][j];  
				}
				  else  //如果放的下要考虑要不要装下他。
				  {
					  c[i][j]=max(c[i-1][j],c[i-1][j-a[i]]+b[i]);
				  }
			}
		}
		printf("%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分

8 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

legend

TA的其他文章

你可能喜欢

C语言训练-亲密数（C语言代码）

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

1065

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

字符逆序（C语言代码）

背包问题（动态规划，超级详细，保证教会）

评论区

精彩推荐

格式错误一万年，，有没有过了的来看看（终于过了）

第一

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

时间转换（Java代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

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

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

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

【魔板】（C++代码）(时间超限，希望会的帮我改正一下)

用筛法求之N内的素数。（C语言代码）

legend

TA的其他文章

你可能喜欢

C语言训练-亲密数 （C语言代码）

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

1065

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

字符逆序 （C语言代码）

背包问题（动态规划，超级详细，保证教会）

评论区

精彩推荐

格式错误一万年，，有没有过了的来看看（终于过了）

第一

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

时间转换 （Java代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数 （C语言代码）

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

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

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

【魔板】 （C++代码）(时间超限，希望会的帮我改正一下)

用筛法求之N内的素数。 （C语言代码）

C语言训练-亲密数（C语言代码）

字符逆序（C语言代码）

　　评论区

时间转换（Java代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

【魔板】（C++代码）(时间超限，希望会的帮我改正一下)

用筛法求之N内的素数。（C语言代码）