hdu1114Piggy-Bank(DP完全背包)
题意：在ACM可以做任何事情，必须准备和预算获得必要的财政支持。这次行动的主要收入来自不可逆绑定金钱（IBM）。背后的想法很简单。每当一些ACM成员有任何小的钱，他把所有的硬币和成小猪银行抛出。你知道，这个过程是不可逆的，不能被删除的硬币没有打破猪。足够长的时间后，应该有足够的现金在小猪银行支付，需要支付的一切，但有一个很大的问题，小猪银行。这是不可能的，以确定多少钱，里面是。因此，我们可能会破坏猪成片，才发现没有足够的钱。显然，我们要避免这种不愉快的情况。唯一的可能性是衡量小猪银行，并尝试猜里面有多少硬币。假设我们能够准确，我们知道所有硬币给定货币的权重确定权重的猪。再有就是一些最低金额在小猪银行的钱，我们可以保证。你的任务是要找出这种最坏的情况下，里面的小猪银行确定的最低数额的现金。我们需要你的帮助。没有更多的过早破裂的猪！
输入包括T检验案件。它们的数量（T）给定的输入文件的第一行上。每个测试案例开始行包含两个整数E和F表示一个空的猪和猪装满硬币的重量。两个权重给定的以克为单位。没有猪的重量超过10公斤，这意味着1 <= E <= F <= 10000。在第二行中的每一个测试的情况下，是一个整数N（1 <= N <= 500），使在给定的货币使用的各种硬币的数目。这正是N行，每指定一个硬币型。这些行包含两个整数，P和W（1 <= P <= 50000，1 <= W <= 10000）。P是货币单位的硬币的值，W是它的重量克数。代码实现：
#include<stdio.h>#include<cstring>using namespace std;#pragma comment(linker,"/STACK:102400000,102400000")#define MAX 10005#define IFN 1000000int dp[MAX];int p[505],w[505];int min(int x,int y){ return(x>y?y:x);}int main(){ //freopen("input.txt","r",stdin); int e,v; int i,j,t; scanf("%d",&t); while(t--) { scanf("%d%d",&e,&v); dp[0]=0;//注意dp[0]要赋值为0； for(i=1;i<=v;i++)dp[i]=IFN; v-=e; int n; scanf("%d",&n); for(i=0;i<n;i++) scanf("%d%d",&p[i],&w[i]); for(i=0;i<n;i++) for(j=w[i];j<=v;j++) { dp[j]=min(dp[j],dp[j-w[i]]+p[i]); } if(dp[v]==IFN)printf("This is impossible.\n"); else printf("The minimum amount of money in the piggy-bank is %d.\n",dp[v]); } return 0;}