内容基本来自http://www.hankcs.com/program/algorithm/poj-3260-the-fewest-coins.html
主要用于加深个人理解
最小货币流通：用面值Vi，个数Ci的硬币购买价格T的商品，假设商店每种面值的硬币都有无限个，求最小货币流通量。
分成两个过程求解：
一：付钱过程：
这个过程中，我们把货币的价格视为背包的重量，价值视为1，问题就转化为了多重背包问题，
见http://www.cnblogs.com/bestefforts/p/8990866.html
// 多重背包转化为二进制的01背包void dp_multiple_pack(int n, int W){ memset(dp_pay, 0x3f, (W + 1) * sizeof(int)); dp_pay[0] = 0; for (int i = 0; i < n; ++i) { int num = C[i]; for (int k = 1; num > 0; k <<= 1) { int mul = min(k, num); for (int j = W; j >= V[i] * mul; --j) { dp_pay[j] = min(dp_pay[j], dp_pay[j - V[i] * mul] + mul); // 价值为1 } num -= mul; } }}
二：找零过程：
找钱阶段，硬币数量不限，在类似的思路下直接视作完全背包问题。
见http://www.cnblogs.com/bestefforts/p/8990866.html
// 完全背包void dp_complete_pack(int n, int W){ memset(dp_change, 0x3f, (W + 1) * sizeof(int)); dp_change[0] = 0; for (int i = 0; i < n; ++i) { for (int j = V[i]; j <= W; ++j) { dp_change[j] = min(dp_change[j], dp_change[j - V[i]] + 1); // "价值总和"最小 } }}
这道题的难点在于W的设置。
这里应用了一个数学原理：鸽笼原理 。
鸽笼原理是说 把多于n+1个的物体放到n个抽屉里，则至少有一个抽屉里的东西不少于两件。
当然他有很多有用的应用场景，例如在本例中：
假设存在一种最优支付方案，给了多于t + max_v * max_v的钱，那么商店就会找回多于max_v * max_v的钱，这些硬币的个数大于max_v。设这些硬币的面值分别为a_i，根据鸽笼原理的应用，硬币序列中存在至少两个子序列，这两个子序列的和分别都能被max_v整除。如果我们直接用长度更小的那个子序列换算为面值为max_v的硬币某整数个，再去替换母序列就能用更少的硬币买到商品，形成矛盾。
因此，W就可以设置为MAX_T + MAX_V * MAX_V。
#includeusing namespace std;const int MAX_T = 10000 + 4;const int MAX_N = 100 + 2;const int MAX_V = 120 + 1;const int INF = 0x3f3f3f3f; int N, T;int V[MAX_N], C[MAX_N]; // 面值和携带个数int max_v; // 最大面值int dp_change[MAX_T + MAX_V * MAX_V]; // dp_change[i] := 商店找钱金额为i时最少硬币数int dp_pay[MAX_T + MAX_V * MAX_V]; // dp_pay[i] := 顾客付钱金额为i时最少硬币数 // 完全背包void dp_complete_pack(int n, int W){ memset(dp_change, 0x3f, (W + 1) * sizeof(int)); dp_change[0] = 0; for (int i = 0; i < n; ++i) { for (int j = V[i]; j <= W; ++j) { dp_change[j] = min(dp_change[j], dp_change[j - V[i]] + 1); // "价值总和"最小 } }} // 多重背包转化为二进制的01背包void dp_multiple_pack(int n, int W){ memset(dp_pay, 0x3f, (W + 1) * sizeof(int)); dp_pay[0] = 0; for (int i = 0; i < n; ++i) { int num = C[i]; for (int k = 1; num > 0; k <<= 1) { int mul = min(k, num); for (int j = W; j >= V[i] * mul; --j) { dp_pay[j] = min(dp_pay[j], dp_pay[j - V[i] * mul] + mul); // 价值为1 } num -= mul; } }} void solve(){ dp_multiple_pack(N, T + max_v * max_v); // 付钱 dp_complete_pack(N, T + max_v * max_v); // 找钱 int ans = INF; for (int i = max_v * max_v; i >= 0; --i) { ans = min(ans, dp_change[i] + dp_pay[T + i]); } if (ans == INF) { ans = -1; } printf("%d\n", ans);} int main(){#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin);#endif scanf("%d%d", &N, &T); for (int i = 0; i < N; ++i) { scanf("%d", &V[i]); max_v = max(max_v, V[i]); } for (int i = 0; i < N; ++i) { scanf("%d", &C[i]); } solve();#ifndef ONLINE_JUDGE fclose(stdin);#endif return 0;}