# 題目: UVa 165 - Stamps

# 題目說明

k 種面額郵票,每張明信片上最多能貼 h 張郵票
n(h, k) 代表從 k 種面額中選擇至多 h 張郵票,使得可以組成面額為 1 2 3 4 ... n 的連續整數明信片
n 的最大值,及是哪 k 種面額的郵票

例如:
h = 3k = 2
則面額 13 可以組成連續最大 7 種面額的明信片
( 11+133+13+1+13+33+3+1 )
當面額為 1214 時,只能組出最大 6

不論 hk 是多少,一定包刮面額為 1 的郵票,不然就無法組成面額為 1 的明信片


INPUT:
每筆測資輸入兩個整數 hk
hk0 時,結束程式


OUTPUT:
輸出能組成最大 n 面額的郵票,與 n 的值

# 解題方法

以下的寫法是使用雙層 dfs 去遍歷所有可能,若使用 dfs + dp 的話能增加效率

stamp 儲存目前的郵票組合,第一層 dfs search 則為遍歷所有郵票組合
maxstamp[i] 儲存第 i 張郵票能從 1 開始數到得最大值
對於 stamp[i + 1] 的範圍為 stamp[i] + 1maxstamp[i] + 1
( stamp[0] 一定為 1maxstamp[0] 一定為 h )
第二層 dfs 為固定郵票組合,遍歷所有可能數量的郵票組合

例如 h = 3k = 2
第一層 dfs 會找出 1 21 31 4 3 種組合
固定 1 2 時,會找出 121+22+21+2+22+2+2 等 6 種組合
以此類推...

# 參考程式碼

#include <iostream>
#include <vector>
#include <iomanip>
#include <map>
using namespace std;
int h, k, maxval;
map<int, int> stamp;
map<int, int> maxstamp;
map<int, int> ans;
vector<bool> check;
void dfs(int cur, int index, int sum)
{
	if (cur == h)
	{
		check[sum] = true;
		return;
	}
	check[sum] = true;
	for (int i = 0; i <= index; ++i) dfs(cur + 1, index, sum + stamp[i]);
}
void search(int index)
{
	if (index == k)
	{
		if (maxstamp[index - 1] > maxval)
		{
			maxval = maxstamp[index - 1];
			ans = stamp;
		}
		return;
	}
	for (int i = stamp[index - 1] + 1; i <= maxstamp[index - 1] + 1; ++i)
	{
		check.assign(200, false);
		stamp[index] = i;
		dfs(0, index, 0);
		int j = 0, num = 0;
		while (check[++j]) ++num;
		maxstamp[index] = num;
		search(index + 1);
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	while (cin >> h >> k, h && k)
	{
		stamp.clear();
		maxstamp.clear();
		maxval = 0;
		stamp[0] = 1;
		maxstamp[0] = h;
		
		search(1);
		for (auto& [key, val] : ans) cout << setw(3) << val;
		cout << " ->" << setw(3) << maxval << "\n";
	}
	return 0;
}

# 參考資料

https://blog.enmingw32.dev/2018/09/15/UVa-165-Stamps/
https://blog.csdn.net/shuangde800/article/details/7755452

更新於