学步园

题意：给定一个重量，和各种钱币的重量，求可以满足给定重量的钱币组合中的最小组合。如果存在组合就求出最小值。

转移方程 

1) f [ j ] 和 f[j-w[i]] 都可达  则 f[j]=min{f[j],f[j-w[i]]+p[i]};

2)f[ j ]不可达 但  f[j-w[i]] 可达  则 f[j]=f[j-w[i]]+p[i]

3) 其余情况  则不作处理

程序：

#include<cstdio>
#include<cmath>
#include<iostream>
#include<conio.h>
using namespace std;
const int maxn=500;
const int maxdp=10010;
int p[maxn],w[maxn];
int dp[maxdp];

int main()
{
	//freopen("in.txt","r",stdin);
	int t;
	scanf("%d",&t);
	while(t--){
		int w1,sum,n;scanf("%d%d%d",&w1,&sum,&n);
		sum-=w1;
		for(int i=0;i<n;i++)scanf("%d%d",&p[i],&w[i]);
		memset(dp,-1,sizeof(int)*(sum+1));
		dp[0]=0;
		for(int i=0;i<n;i++){
			for(int j=w[i];j<=sum;j++){
				if(dp[j]!=-1&&dp[j-w[i]]!=-1)dp[j]=min(dp[j],dp[j-w[i]]+p[i]);
				else if(dp[j-w[i]]!=-1)dp[j]=dp[j-w[i]]+p[i];
			}
		}
		if(dp[sum]==-1)puts("This is impossible.");
		else printf("The minimum amount of money in the piggy-bank is %d.\n",dp[sum]);
	}
	
}