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

直接上代码：

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

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

代码语言：javascript复制

//万能头文件
#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;
}

cout int 排序 算法 容器

0 人点赞