As a reward for record milk production, Farmer John has decided to start paying Bessie the cow a small weekly allowance. FJ has a set of coins in N (1 <= N <= 20) different denominations, where each denomination of coin evenly divides the next-larger denomination (e.g., 1 cent coins, 5 cent coins, 10 cent coins, and 50 cent coins).Using the given set of coins, he would like to pay Bessie at least some given amount of money C (1 <= C <= 100,000,000) every week.Please help him ompute the maximum number of weeks he can pay Bessie.
Input
* Line 1: Two space-separated integers: N and C
* Lines 2..N+1: Each line corresponds to a denomination of coin and contains two integers: the value V (1 <= V <= 100,000,000) of the denomination, and the number of coins B (1 <= B <= 1,000,000) of this denomation in Farmer John's possession.
* Lines 2..N+1: Each line corresponds to a denomination of coin and contains two integers: the value V (1 <= V <= 100,000,000) of the denomination, and the number of coins B (1 <= B <= 1,000,000) of this denomation in Farmer John's possession.
Output
* Line 1: A single integer that is the number of weeks Farmer John can pay Bessie at least C allowance
Sample Input
3 6 10 1 1 100 5 120
贪心。大概都能想到。关键是如何寻找最优策略。对于面值大于c的硬币自然不用说。一枚用一周。
对于面值小于c的硬币。我们先考虑一个c的方案。要使用的周数最多我们应该就要使钱的利用率最大。
也就是说损失的钱最少。尽量不要超过c太多。在不超过c的情况下对于大面值和小面值的优先使用大面值的。应为小面值的组合可得到大面值的(整除关系)。留下小面值的给后面的组合最优的可能性越大。如这种策略下没凑够c的话就
找一个最小的面额。使得组合值大于c。(使损失值最小)http://www.hankcs.com/program/cpp/poj-3040-allowance.html
农夫约翰要给奶牛Bessie发工资了，每周至少 C 元。约翰手头上有面值V_i的硬币B_i个，这些硬币的最小公约数为硬币的最小面值。求最多能发几周？
贪心策略是使多发的面额最小（最优解）。分三个阶段：
- 首先面额不小于C的硬币属于没办法节约的类型，先统统发掉。
- 然后对硬币面额从大到小尽量凑得接近C，允许等于或不足C，但是不能超出C。
- 接着按硬币面额从小到大凑满C（凑满的意思是允许超出一个最小面值，ps此处的最小面值指的是硬币剩余量不为0的那些硬币中的最小面值），凑满之后得出了最优解，发掉，进入步骤2.
这样就保证了每次都是当前的最优解，这个题很好地体现了贪心法的精髓。
typedef pair<int, int> Coin; // 硬币 面值和数量Coin coin[20];int need[20];int main(int argc, char *argv[]){#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);#endif int N, C; cin >> N >> C; for (int i = 0; i < N; ++i) { cin >> coin[i].first >> coin[i].second; } int week = 0; // 面额不小于C的一定可以支付一周 for (int i = 0; i < N; ++i) { if (coin[i].first >= C) { week += coin[i].second; coin[i].second = 0; } } sort(coin, coin + N, greater<Coin>()); while(true) { int sum = C; // 等待凑足的sum memset(need, 0, sizeof(need)); // 从大到小 for (int i = 0; i < N; ++i) { if (sum > 0 && coin[i].second > 0) { int can_use = min(coin[i].second, sum / coin[i].first); if (can_use > 0) { sum -= can_use * coin[i].first; need[i] = can_use; } } } // 从小到大 for (int i = N - 1; i >= 0; --i) { if (sum > 0 && coin[i].second > 0) { int can_use = min(coin[i].second - need[i], // 上个loop用掉了一些 (sum + coin[i].first - 1) / coin[i].first); // 允许多出不超过一个面值的金额 if (can_use > 0) { sum -= can_use * coin[i].first; need[i] += can_use; } } } if(sum > 0) { break; } int add_up = numeric_limits<int>::max(); // 凑起来的week数 // add_up多少个最优的week 受限于 每种面值能满足最优解下的需求个数多少次 for (int i = 0; i < N; ++i) { if (need[i] == 0) { continue; } add_up = min(add_up, coin[i].second / need[i]); } week += add_up; // 最优解生效，更新剩余硬币数量 for (int i = 0; i < N; ++i) { if (need[i] == 0) { continue; } coin[i].second -= add_up * need[i]; } } cout << week << endl;#ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); system("out.txt");#endif return 0;}
Also check http://www.tuicool.com/articles/Vv6nQj
Read full article from 3040 -- Allowance