POJ 3040 Allowance 题解 《挑战程序设计竞赛(第2版)》

2.2 一往直前！贪心法 其他

POJ 3040 Allowance

农夫约翰要给奶牛Bessie发工资了（你们结婚吧，生个牛头人(￣_￣|||) ），每周至少 C 元。约翰手头上有面值V_i的硬币B_i个，这些硬币的最小公约数为硬币的最小面值。求最多能发几周？

贪心策略是使多发的面额最小（最优解）。分三个阶段：

1. 首先面额不小于C的硬币属于没办法节约的类型，先统统发掉。

2. 然后对硬币面额从大到小尽量凑得接近C，允许等于或不足C，但是不能超出C。

3. 接着按硬币面额从小到大凑满C（凑满的意思是允许超出一个最小面值，ps此处的最小面值指的是硬币剩余量不为0的那些硬币中的最小面值），凑满之后得出了最优解，发掉，进入步骤2.

这样就保证了每次都是当前的最优解，这个题很好地体现了贪心法的精髓。

不过话说回来，约翰你那么喜欢奶牛，你们干脆结婚算了吧……

#include <iostream>
#include <functional>
#include <algorithm>
#include <limits>
using namespace std;

typedef pair<int, int> Coin;	// 硬币 面值和数量
Coin coin[20];
int need[20];

///////////////////////////SubMain//////////////////////////////////
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;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 3040 Allowance 题解 《挑战程序设计竞赛(第2版)》