UVa 674 : Coin Change

Posted on | In |  
Symbols : 617 字

給定面額為 1, 5, 10, 25, 50 的 5 種硬幣，輸入一個金額大小，要計算出使用這 5 種硬幣組合出此金額的方法數，並輸出。

測資
Input :

11
26

Output :

4
13


解法

這是典型的完全背包問題，和 01 背包問題不同的地方是硬幣是可以無限使用的，而 01 背包問題只能使用一次。

01 背包問題思考角度 : 考慮第 k 種物品，取或不取

狀態轉移方程 : value[k][w] = max{ value[k-1][w] (不取k), value[k-1][w - weight[k]] + item_val[k] (取k) }
value[k][w] : value[k][w]為取前 k 種硬幣與重量限制為 w 的情況下的最大價值
weight[k] : 物品 k 的重量
item_val[k] : 物品 k 的價值

而完全背包問題則否，所以需要換一個角度思考
當計算到 t cents 時，因為每一個硬幣都是可以無限拿取的，因此我們可以考慮 2 種計算方法

  1. 令 t + coin_type[k] 的方法數增加一種，因為可以從 t 再加上 coin_type[k]
  2. 令 t 的方法數增加一種，因為可以從 t - coin_type[k] 再加上 coin_type[k]

如果忽略檢測陣列範圍值所消耗的時間的話，這 2 種方法的時間複雜度皆為 O(N2)
但這 2 種方法的本質我覺得還是不太一樣的

  • 方法一比較屬於暴力法，從當前進度點出發去建構更深的答案。( 有點抽象發散的 fu )
    此外，當我們的問題範圍最大只到 t 時，這種方法會做出多餘的事情。
    例如有 1, 5, 10 三種硬幣，我們要計算 11 的答案，但當我們在計算 10 時，多計算了 10+5 與 10+10。
  • 方法二就是屬於動態規劃，從子問題去建構出最佳解答。( 聚合的 fu )
    並且不會有多餘的計算。


程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:
	Solution() : coin_types{ 1,5,10,25,50 }, methods(MAX_CENTS + 1, 0)
	{
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout.tie(nullptr);

		initial_methods();
	}

	int calculate(int num) const
	{
		return methods[num];
	}

private:
	const int MAX_CENTS = 7489;

	const vector<int> coin_types;
	vector<int> methods;

	void initial_methods(void)
	{
		// note this!!!!
		methods[0] = 1;

		for (auto coin : coin_types)
			for (int now_value = coin; now_value <= MAX_CENTS; ++now_value)
				methods[now_value] += methods[now_value - coin];
	}
};

int main(void)
{
	Solution s;

	int num;

	while (cin >> num)
	{
		cout << s.calculate(num) << '\n';
	}

	cout << flush;
	
	return 0;
}
0%