完全背包
#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; }