# 題目: 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
種
不論 h
與 k
是多少,一定包刮面額為 1
的郵票,不然就無法組成面額為 1
的明信片
INPUT:
每筆測資輸入兩個整數 h
與 k
當 h
與 k
為 0
時,結束程式
OUTPUT:
輸出能組成最大 n
面額的郵票,與 n
的值
# 解題方法
以下的寫法是使用雙層 dfs
去遍歷所有可能,若使用 dfs + dp
的話能增加效率
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 4
3 種組合
固定 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