O(VN)的完全背包，注意题目限制条件：物品总cost恰好达到V，一开始还优化了一下， 把val小cost大的物品去掉了，后来一想这样会产生错误的结果
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int INF = 0x3f3f3f3f; const int MAXN = 500 + 10; const int MAXV = 10000 + 10; int T, N, V, dp[MAXV]; struct Item { int val, cost; }item[MAXN]; int main() { scanf("%d", &T); for (int kase = 1; kase <= T; kase++) { int a, b; scanf("%d %d", &a, &b); V = b - a; scanf("%d", &N); for (int i = 1; i <= N; i++) { scanf("%d %d", &item[i].val, &item[i].cost); } for (int i = 1; i <= V; i++) dp[i] = INF; for (int i = 1; i <= N; i++) { for (int j = item[i].cost; j <= V; j++) { dp[j] = min(dp[j], dp[j - item[i].cost] + item[i].val); } } if (dp[V] == INF) printf("This is impossible.\n"); else { printf("The minimum amount of money in the piggy-bank is %d.\n", dp[V]); } } return 0; }