放牧代码和思想
专注自然语言处理、机器学习算法

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版)》

分享到:更多 ()

评论 5

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #2

    那啥,从小到大贪的时候,一旦出现第一个可以取的面额的时候就可以break了,因为从大到小贪已经保证了“只要再加上最小的面额,就会大于C”。还是赞博主

    karia2年前 (2016-01-12)回复
    • 不一定喔。因为从小到大贪的时候,出现的第一个可以取的面额的硬币的数量不一定够用,还是要再往上面找找。

      清和9个月前 (02-10)回复
  2. #1

    赞,po主思路清晰

    jerry2年前 (2015-10-06)回复

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机