以dfs解决01背包——PAT(AdvancedLevel)1068FindMoreCoins(30分)

题目概述&＃xff1a;
给一组数&＃xff0c;判断是否存在其中最小的一组子数列之和为给定数

题目分析&＃xff1a;
dfs&＃xff0c;为了找出最小的一组&＃xff0c;我们从小到大排&＃xff0c;这种情况下找出的第一个解即为最小的&＃xff0c;同时利用flag进行记录&＃xff0c;及时停止其他无效搜索。

dfs分析&＃xff1a;

void dfs(int cur, vector<int> path, int w)//cur是当前浏览的位置&＃xff0c;path是累积路径&＃xff0c;w是累计和
{//无效退出if(flag &＃61;&＃61; true || w > m) return;//唯一性标识vis[cur] &＃61; true;//有效退出if(w &＃61;&＃61; m && flag &＃61;&＃61; false){flag &＃61; true;res &＃61; path;return;}//不重复迭代for(int i &＃61; 1; i <&＃61; k; i&＃43;&＃43;){if(!vis[i]){path.push_back(coin[i]);dfs(i, path, w &＃43; coin[i]);//往第i个深搜vis[i] &＃61; false;path.pop_back();//回溯退回}}return;
}

参数解释&＃xff1a;cur表示当前所指位置&＃xff08;初始可设为0&＃xff09;&＃xff0c;path表示累计搜索路线&＃xff0c;w表示累加和

无效退出&＃xff1a;已找到答案或和超出

有效进入&＃xff1a;设置vis为true

有效退出&＃xff1a;第一次找到w &＃61;&＃61; m&＃xff0c;将path存进res&＃xff0c;同时设flag为真

迭代&＃xff1a;对未搜索的点&＃xff0c;
1.加入path
2.迭代进下一层dfs
3.回溯&＃xff08;包括重置vis和pop_back&＃xff09;

两处剪枝&＃xff1a;

1.总和不够

if(sum < m){cout << "No Solution" << endl;return 0;}


2.过滤掉大于m的单值

//第二处剪枝k &＃61; n;//k的初值,k为有效的最后一个值for(int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;){if(coin[i] > m){k &＃61; i - 1;break;}}


开启dfs&＃xff1a;

dfs(0, res, 0);//新增一个不存在的0起点


数组从1开始记起&＃xff0c;0起点可作为启动起点

完整代码&＃xff1a;

#include
using namespace std;vector<int> res;//记录最终路径
bool vis[10010];//保证不重复
int coin[10010];//记录面值
bool flag &＃61; false;//记录是否找到
int k;//剪枝&＃xff0c;记录有效的位置
int m;//记录targetvoid dfs(int cur, vector<int> path, int w)//cur是当前浏览的位置&＃xff0c;path是累积路径&＃xff0c;w是累计和
{//无效退出if(flag &＃61;&＃61; true || w > m) return;//唯一性标识vis[cur] &＃61; true;//有效退出if(w &＃61;&＃61; m && flag &＃61;&＃61; false){flag &＃61; true;res &＃61; path;return;}//不重复迭代for(int i &＃61; 1; i <&＃61; k; i&＃43;&＃43;){if(!vis[i]){path.push_back(coin[i]);dfs(i, path, w &＃43; coin[i]);//往第i个深搜vis[i] &＃61; false;path.pop_back();//回溯退回}}return;
}int main()
{int n;cin >> n >> m;int sum &＃61; 0;for(int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;){cin >> coin[i];sum &＃43;&＃61; coin[i];}//第一处剪枝if(sum < m){cout << "No Solution" << endl;return 0;}else{sort(coin &＃43; 1, coin &＃43; n &＃43; 1);//从小到大排//第二处剪枝k &＃61; n;//k的初值,k为有效的最后一个值for(int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;){if(coin[i] > m){k &＃61; i - 1;break;}}//开始dfsdfs(0, res, 0);//新增一个不存在的0起点if(flag &＃61;&＃61; true){cout << res[0];for(int i &＃61; 1; i < res.size(); i&＃43;&＃43;)cout << " " << res[i];cout << endl;}else cout << "No Solution" << endl;}return 0;
}


总结&＃xff1a;
1.res记录路径&＃xff0c;vis记录是否走过&＃xff0c;flag记录是否找到
2.剪枝&＃xff1a;总和、个体、第一次找到
3.dfs套路&＃xff1a;无效退出&＃xff0c;有效进入&＃xff0c;有效退出&＃xff0c;无重复迭代
4.dfs迭代套路&＃xff1a;加入累计路径&＃xff0c;下一轮迭代&＃xff0c;回溯&＃xff08;vis&＃43;pop&＃xff09;
5.dfs参数套路&＃xff1a;当前位置&＃xff0c;累计路径&＃xff0c;累计统计量
6.dfs开启套路&＃xff1a;当前位置可加入无意义的初始启动点&＃xff0c;如0