小猪储蓄罐.哈哈哈！
题目大意：给出空的储蓄罐和满的储蓄罐的重量。给出n中硬币，每种硬币的value和weight，求出满足重量的最小value和，如果不能满足就输出“This is impossible.”。
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> using namespace std; #define INF 1e8 int v[600], w[600], dp[10050]; int main() { int t, n, sum, emp, full; cin >> t; while(t--) { scanf("%d%d", &emp, &full); scanf("%d", &n); for(int i = 0; i < n; i++) scanf("%d%d", &v[i], &w[i]); sum = full - emp; fill(dp, dp+sum+1, INF); dp[0] = 0; for(int j = 0; j < n; j++) { for(int k = 0; k <= sum; k++) { if(k >= w[j]) dp[k] = min(dp[k], dp[k-w[j]]+v[j]); } } if(dp[sum] == INF) printf("This is impossible.\n"); else printf("The minimum amount of money in the piggy-bank is %d.\n",dp[sum]); } return 0; }
