首页 > 其他 > 详细

hdu2191 悼念512汶川大地震遇难同胞——珍惜现在,感恩生活

时间:2014-06-22 21:39:05      阅读:318      评论:0      收藏:0      [点我收藏+]

转载请注明出处:http://blog.csdn.net/u012860063

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2191

多重背包转换为01背包问题:

代码如下:

#include <cstdio>
#include <cstring>
#define N 247
int max(int a,int b)
{
	if(a > b)
		return a;
	else return b;
}
int main()
{
	int t,n,m,i,j,k;
	int w[N],pri[N],num[N],f[N];
	while(~scanf("%d",&t))
	{
		while(t--)
		{
			memset(f,0,sizeof(f));
			scanf("%d%d",&n,&m);//n为总金额,m为大米种类
			for(i = 0 ; i < m ; i++)
			{
				scanf("%d%d%d",&pri[i],&w[i],&num[i]);//num[i]为每种大米的袋数
			}
			for(i = 0 ; i < m ; i++)
			{
				for(k = 0 ; k < num[i] ; k++)
				{
					for(j = n ; j >= pri[i]; j--)
					{
						f[j] = max(f[j],f[j-pri[i]]+w[i]);
					}
				}
			}
			printf("%d\n",f[n]);
		}
	}
	return 0;
}



hdu2191 悼念512汶川大地震遇难同胞——珍惜现在,感恩生活,布布扣,bubuko.com

hdu2191 悼念512汶川大地震遇难同胞——珍惜现在,感恩生活

原文:http://blog.csdn.net/u012860063/article/details/32912621

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!