团体程序设计天梯赛
L3-001 凑零钱
两种做法，介绍一下第一种。
法一：dfs+剪枝。这种做法在最后一个测试点会超时，最后一个测试点对应的情况是所有的零钱加起来都不能满足要求，单独判断这种情况可AC. 这种做法的步骤是，首先读取零钱数据，同时加和，读取完成后判断和是否小于题目所要求的值，是则直接输出结果。否则，对存储零钱的数组排序，接着dfs，在这个过程中实时同步存储结果的数组res和存储当前零钱总和的变量sum，如果出现加上某个节点的值的结果大于所要求的值时，说明这之后搜索的值也都大于该值，所以可以剪枝；如果小于所要求的值时，还没有搜索到val数组（顺序存储零钱的数组）的最后一个值，则递归搜索其儿子节点，反之迭代父节点的下一个值。（这是一种思路，事实上，可以进一步优化，见下文）
#include <bits/stdc++.h>
using namespace std;
vector<int> val, res;
int n, m, flag = 0, sum = 0;
void dfs(int node){
sum += val[node];
res.push_back(val[node]);
if(sum == m){
for(int i = 0; i <= (int)res.size() - 1; i++)
cout << res[i] << " \n"[i == (int)res.size() - 1];
flag = 1;
return;
}
else if(sum > m){
res.pop_back();
sum -= val[node];
return;
}
else{
if(node == n - 1){
res.pop_back();
sum -= val[node];
return;
}
dfs(node + 1);
if(flag) return;
else{
res.pop_back();
sum -= val[node];
dfs(node + 1);
}
}
}
int main(){
cin >> n >> m;
val.resize(n);
int preSum = 0;
for(int i = 0; i <= n - 1; i++){
cin >> val[i];
preSum += val[i];
}
if(preSum < m) cout << "No Solution" << endl;
else{
sort(val.begin(), val.end());
dfs(0);
if(!flag) cout << "No Solution" << endl;
}
return 0;
}
注：这是比较容易想到的一种解法，可以进一步剪枝。比如有五个数，1~5，一直迭代，发现直到1235，其和都是偏大的，所以迭代1245，如果这时其和偏小，那么125没有必要迭代，因为4的下一个数恰好是5，它之前就在这个求和的式子中了，所以式子并不会更大，不会满足要求；但是如果是1235偏小，它的下一个迭代1245是值得尝试的。综上，可以进一步剪枝，当发现搜索到最后一个节点，求和值较小时，向上判断，如果上面的一个节点的下一个迭代不为本节点时，进行迭代；否则继续回溯，也就是进行了剪枝。这样的算法可以直接ac，不需要多余的判断。
#include <bits/stdc++.h>
using namespace std;
vector<int> val, res;
int n, m, flag = 0, sum = 0, tempNode;
void dfs(int node){
sum += val[node];
res.push_back(val[node]);
if(sum == m){
for(int i = 0; i <= (int)res.size() - 1; i++)
cout << res[i] << " \n"[i == (int)res.size() - 1];
flag = 1;
return;
}
else if(sum > m){
res.pop_back();
sum -= val[node];
return;
}
else{
if(node == n - 1){
flag = 2;
tempNode = node;
res.pop_back();
sum -= val[node];
return;
}
dfs(node + 1);
if(flag == 1) return;
else if(flag == 2){
if(node == tempNode - 1){
tempNode = node;
return;
}
else{
flag = 0;
res.pop_back();
sum -= val[node];
dfs(node + 1);
}
}
else{
res.pop_back();
sum -= val[node];
dfs(node + 1);
}
}
}
int main(){
cin >> n >> m;
val.resize(n);
for(int i = 0; i <= n - 1; i++) cin >> val[i];
sort(val.begin(), val.end());
dfs(0);
if(!(flag == 1)) cout << "No Solution" << endl;
return 0;
}