# 題目: UVa 165 - Stamps

# 題目說明

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

例如:
h = 3及k = 2
則面額1與3可以組成連續最大7種面額的明信片
( 1、1+1、3、3+1、3+1+1、3+3、3+3+1 )
當面額為1與2或1與4時，只能組出最大6種

---

INPUT:
每筆測資輸入兩個整數h與k
當h與k為0時，結束程式

---

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

# 解題方法

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

例如h = 3及k = 2時
第一層dfs會找出1 2、1 3、1 43種組合
固定1 2時，會找出1、2、1+2、2+2、1+2+2、2+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