b511 - 換銅板
題目描述
題目要求找出所有可能的銅板組合，使得這些銅板的總價值等於給定的金額。輸入包含不同面值的銅板數量、每種銅板的面值以及需要找零的總金額。輸出所有符合條件的銅板組合，按照特定順序排列。
解題思路
此題可以使用深度優先搜尋 (DFS) 或回溯法來解決。我們遞迴地嘗試每種面值的銅板，並記錄使用該面值銅板的數量。在遞迴過程中，我們不斷減少需要找零的金額，直到金額為零或所有面值的銅板都已考慮完畢。如果金額為零，則找到一個有效的組合，並將其輸出。由於題目要求特定的輸出順序，因此在遞迴過程中，我們需要按照銅板面值的順序進行遍歷。
複雜度分析
- 時間複雜度: O(n^total)，其中 n 是銅板面值的數量，total 是需要找零的總金額。在最壞的情況下，我們可能需要嘗試所有可能的銅板組合。
- 空間複雜度: O(n)，主要用於儲存當前銅板組合的數量以及遞迴調用的堆疊空間。
程式碼
#include <iostream>
using namespace std;
int c[5],n,total,ans[5];
void dfs(int now,int it){
if(now<0)return;
if(now==0){
cout << "(";
for(int i=0;i<n-1;++i)
cout << ans[i] << ",";
cout << ans[n-1] << ")\n";
return;
}
if(it>=n)return;
int mt=now/c[it];
for(int i=0;i<=mt;++i){
ans[it]=i;
dfs(now-c[it]*i,it+1);
}
}
int main(){
while(cin >> n ){
for(int i=0;i<n;++i)
cin >> c[i];
cin >> total;
dfs(total,0);
}
}