题意： 已知一些硬币的面值和重量，问一定重量的硬币的最小价值。
题解： 每次拿到dp的题目，都下意识想排个序然后贪心做。 当然不可以贪心，也没必要排序。因为求的是最小值，所以初始化要赋无穷大，但是dp[0] = 0。然后就是裸的完全背包了。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f; #define endl "\n" #define dbg(x...) \ do { \ cout << #x << " -> "; \ err(x); \ } while (0) void err() { cout << endl;} template <class T, class... Ts> void err(const T& arg, const Ts&... args) { cout << arg << ' '; err(args...); } inline int read() { int s = 0, w = 1; char ch = getchar(); while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();} while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar(); return s * w; } const int N = 1e5 + 10; const int M = 510; int dp[N]; int p[M], w[M]; void run() { memset(dp, inf, sizeof dp); dp[0] = 0; int e = read(), f = read(); f -= e; int n = read(); for(int i = 1; i <= n; i++){ p[i] = read(), w[i] = read(); } for(int i = 1; i <= n; i++){ int P = p[i], W = w[i]; for(int j = W; j <= f; j++){ dp[j] = min(dp[j], dp[j - W] + P); } } if(dp[f] == inf) printf("This is impossible.\n"); else printf("The minimum amount of money in the piggy-bank is %d.\n", dp[f]); } int main() { int _T = read(); while(_T--) run(); return 0; }