|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include <iostream> #include <sstream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <map> #include <list> #include <stack> using namespace std; struct coinType{ int w; int v; coinType(int iv,int iw){ v = iv; w = iw; } }; vector<coinType> coin; int dp[10005]; int main(){ int caseCnt; cin >> caseCnt; while (caseCnt--) { int e = 0,f = 0,n = 0; cin >> e >> f >> n; coin.clear(); int iv = 0,iw = 0; for (int i = 0; i < n; i++) { cin >> iv >> iw; coin.push_back(coinType(iv,iw)); } int w = f - e; memset(dp, 0x3f3f, sizeof(dp)); dp[0] = 0; for (int i = 1; i <= w; i++) { for (int j = 0; j < n; j++) { if (i < coin[j].w) { continue; } dp[i] = min(dp[i-coin[j].w]+coin[j].v,dp[i]); } } if (dp[w] == 0x3f3f3f3f) { cout << "This is impossible." << endl; }else{ cout << "The minimum amount of money in the piggy-bank is " << dp[w] << '.' << endl; } } return 0; } |
这个基本上还是01背包嘛，但是这回我把状态的判定条件设置为在一定重量的情况下，尽量让硬币的总价值更少。
