回溯算法求解0-1背包问题时的剪枝方案

直接上代码：

1、左边界剪枝，排序商品。理解不是排列是组合。

2、右边界剪枝，找到一种选择，其它子节点不再访问。

//万能头文件#include <bits/stdc++.h>#include <algorithm> //算法库 ACM using namespace std;//背包容器int wei=50;struct Good { int w; int v; int isSel;};Good goods[3];int res[100]= {-1};

void init() { //不是排列是组合 goods[0]= {10,20,0}; goods[1]= {20,15,0}; goods[2]= {40,10,0};}

void show(int n) { cout<<"--------------------------"<<endl; for(int i=1; i<=n; i++) { cout<< goods[ res[i] ].w <<"-"<<goods[ res[i] ].v <<endl; } cout<<"*******************"<<endl;}int maxVal=0; int ans=0;void dfs(int idx,int wei,int dept,int sum) {//idx 用于左边界剪枝 for(int i=idx; i<3 ; i++ ) { if( goods[i].isSel==1 )continue; //可选择 goods[i].isSel=1; res[dept]=i; //是否选择 if(wei- goods[i].w ==0) { cout<<sum+goods[i].v<<endl; ans=max(ans,sum+goods[i].v); show(dept);break;//右边界剪枝 } else if( wei- goods[i].w <0 ) { //选择结束 cout<<sum<<endl; ans=max(ans,sum); show(dept-1); break;//右边界剪枝 } else { //继续选择 dfs(i+1,wei- goods[i].w,dept+1,sum+goods[i].v); } goods[i].isSel=0; res[dept]=-1; }}int main() { init(); dfs(0,wei,1,0); cout<<"-----------"<<endl; cout<<ans; return 0;}