学步园

完全背包问题

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

注意边界的处理

#include<stdio.h>
#include<string.h>

const inf=999999;
int min(int a,int b)
{
	return a>b? b:a;
}

int main()
{
	int t,i,j,d1,d2,n;
	int w[510],v[510];
	int dp[10500];

	while(scanf("%d",&t)!=EOF)
	{
		while(t--)
		{
			scanf("%d %d",&d1,&d2);
			scanf("%d",&n);

			for(i=0;i<=(d2-d1);i++)//注意边界
				dp[i]=inf;
			dp[0]=0;

			for(i=0;i<n;i++)
				scanf("%d %d",&v[i],&w[i]);
			for(i=0;i<n;i++)//完全背包
			{
				for(j=w[i];j<=d2-d1;j++)
				{
					dp[j]=min(dp[j],dp[j-w[i]]+v[i]);
				}
			}
			if(dp[d2-d1]==inf)
				printf("This is impossible.\n");
			else
				printf("The minimum amount of money in the piggy-bank is %d.\n",dp[d2-d1]);
		}
	}
return 0;
}