现在的位置: 首页 > 综合 > 正文

hdu 1114 Piggy-Bank

2018年12月29日 ⁄ 综合 ⁄ 共 457字 ⁄ 字号 评论关闭

完全背包

 

 

 

 

#include<stdio.h>
#define inf 0x3fffffff
int dp[10010];
int main()
{
	int i,j,n,w[501],v[501],w1,w2,t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&w1,&w2);
		scanf("%d",&n);
		for(i=0;i<n;i++)
			scanf("%d%d",&w[i],&v[i]);
		for(i=0;i<=w2-w1;i++)
			dp[i]=inf;
		dp[0]=0;
		for(i=0;i<n;i++)
			for(j=v[i];j<=w2-w1;j++)
			{
				if(dp[j]>dp[j-v[i]]+w[i])
					dp[j]=dp[j-v[i]]+w[i];
			}
			if(dp[w2-w1]==inf)
				puts("This is impossible.");
			else printf("The minimum amount of money in the piggy-bank is %d.\n",dp[w2-w1]);
	}
	return 0;
}

 

抱歉!评论已关闭.