hdu1114完全背包

题意：已知一个猪仔储钱罐空载时的质量和满载时的质量，给出猪仔储钱罐中有可能出现的硬币种类，每种硬币都有自身的质量和价值，问当一个猪仔储钱罐满载时内面最少有的硬币的总价值。
解题思路：这是一个完全背包问题，因为硬币是可以无限装，那么所求的是最小值，就把初始状态都设为无限大，只有0状态为0，然后只有现态不为无穷大的时候，才就去找次态与现态+1的最小值，然后就是模板的事了。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n,w[505], m,c[505],dp[10005];
int main()
{
int sum,t,i,j;
scanf("%d",&t);
while(t--)
{
scanf("%d %d",&m,&sum);
sum=sum-m;
for(i=1;i<=sum;i++)
dp[i]=25000010;
dp[0]=0;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d %d",&w[i],&c[i]);
for(i=0;i<n;i++)
for(j=c[i];j<=sum;j++)
if(dp[j-c[i]]<=25000000)
dp[j]=min(dp[j],dp[j-c[i]]+w[i]);
if(dp[sum]>25000000)
printf("This is impossible.\n");
else
printf("The minimum amount of money in the piggy-bank is %d.\n",dp[sum]);
}
return 0;
}

本文出自 “Qero” 博客，请务必保留此出处http://8590696.blog.51cto.com/8580696/1358903

hdu1114完全背包

原文：http://8590696.blog.51cto.com/8580696/1358903