https://vjudge.csgrandeur.cn/problem/POJ-3040

/*
作為創(chuàng)紀(jì)錄的牛奶產(chǎn)量的獎勵，約翰決定每周給貝西一小筆零用錢。FJ擁有一組N（1 <= N <= 20）種不同面額的硬幣，
其中每個面額的硬幣均可整除較大面額的硬幣（例如，1分硬幣、5分硬幣、10分硬幣和50分硬幣）。
使用給定的硬幣面額，他想每周至少支付給貝西一定金額C（1 <= C <= 100,000,000）。
請幫助他計算他最多可以支付貝西多少周。

輸入

第1行：兩個以空格分隔的整數(shù)：N和C
第2行到第N+1行：每行對應(yīng)一個硬幣面額，并包含兩個整數(shù)：
硬幣面額V（1 <= V <= 100,000,000）和約翰手中該面額的硬幣數(shù)量B（1 <= B <= 1,000,000）。
輸出

第1行：一個整數(shù)，表示約翰可以支付貝西至少C零用錢的周數(shù)。

3 6
10 1
1 100
5 120

111

3 6
10 3
20 4
40 5

12

3 51
100 1
50 4
1 2

4


3 51
1 2
50 4
100 1

4

20 100000000
67108864 1000000
33554432 1000000
16777216 1000000
8388608 1000000
4194304 1000000
2097152 1000000
1048576 1000000
524288 1000000
262144 1000000
131072 1000000
65536 1000000
32768 1000000
16384 1000000
8192 1000000
4096 1000000
2048 1000000
1024 1000000
512 1000000
256 1000000
128 1000000

1340054


輸入詳情：
FJ每周想支付給貝西6美分。他手上有100個1美分硬幣，120個5美分硬幣和1個10美分硬幣。

輸出詳情：
FJ可以用一個10美分硬幣多支付給貝西1周，然后用兩個5美分硬幣支付給貝西10周，
最后用一個1美分硬幣和一個5美分硬幣支付給貝西100周。
*/

解答
直覺分析如下：
因為可選擇的美分硬幣數(shù)值是可整除的。所以我們需要盡量選擇面額更大的硬幣.
1 因為面值小的硬幣總能替代面額大的硬幣，更優(yōu)。所以我們選擇次優(yōu)的較大面額的硬幣，將更優(yōu)的選擇留給后面。
2 同樣的 湊齊剛好等于每周報酬的面值能留下更多的硬幣數(shù)值給后面的選擇,所以優(yōu)先選擇剛好等于每周報酬的組合，
然后再選擇最接近、大于等于每周報酬的組合。
代碼如下

#include <iostream>
#include <cstring>
#include <map>

using namespace std;

int n, c;
int ans;
map<int, int> mm;
map<int, int> usedmm;
int limit;

void GetusedArr() {
	//計算每次選擇硬幣的組合  逆序從大到小選擇， 優(yōu)先選擇大額的 最接近等于每周報酬的組合
	for (map<int, int>::reverse_iterator it = mm.rbegin(); it != mm.rend(); it++) {
		if (it->second != 0 && limit >0  && limit >= it->first) {
			int used = min(limit / it->first, it->second);
			limit -= used * it->first;
			usedmm[it->first] += used;
		}
        //剩余值為0  則說明抽出了剛好等于每周報酬的組合
		if (limit == 0) break;
	}

	//貪心完所有金幣 還沒超出需要的金額. 說明湊不出剛好等于報酬的組合
    // 從小到大選擇硬幣，使用較小的面值進行填充 最接近等于每周報酬
	if (limit > 0) {
		for (map<int, int>::iterator it = mm.begin(); it != mm.end(); it++) {
			if (it->second > 0 && limit > 0 && mm[it->first] > usedmm[it->first]) {
				int used = 1;  int v = it->first; int cnt = it->second;
				limit -= v;
				usedmm[v] += 1;
			}
		}
	}

	return;
}

void solve() {

	while (1) {
		usedmm.clear();
		limit = c;
		GetusedArr();
        //limit 還不等于小于0  那么說明現(xiàn)在的硬幣已經(jīng)不能湊齊一周報酬了
		if (limit > 0) {
			cout << ans << endl; return;
		}
		//按照usedmm  查看能取幾次
		int minget = 1000010;
		for (map<int, int>::iterator it = usedmm.begin(); it != usedmm.end(); it++) {
			int v = it->first;
			minget = min(minget, mm[v]/it->second);
		}
	
		ans += minget;

		//從已有的硬幣里減去
		for (map<int, int>::iterator it = usedmm.begin(); it != usedmm.end(); it++) {
			int v = it->first;
			mm[v] -= minget * it->second;
		}
	}
}

int main()
{
	cin >> n >> c;

	for (int i = 0; i < n; i++) {
		int v, b; cin >> v >> b;
		if (v >= c) {
			ans += b;
		}
		else {
			mm[v] += b;
		}
	}

	solve();


	return 0;
}

我的視頻題解空間文章來源地址http://www.zghlxwxcb.cn/news/detail-711385.html

到了這里，關(guān)于挑戰(zhàn)程序設(shè)計競賽 2.2 poj 3040 Allowance 貪心的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！