前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >回溯算法求解0-1背包问题时的剪枝方案

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

作者头像
一枚大果壳
发布2024-01-31 15:33:51
1290
发布2024-01-31 15:33:51
举报
文章被收录于专栏:编程驿站编程驿站

直接上代码:

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;
}
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2024-01-29,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 编程驿站 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
容器服务
腾讯云容器服务(Tencent Kubernetes Engine, TKE)基于原生 kubernetes 提供以容器为核心的、高度可扩展的高性能容器管理服务,覆盖 Serverless、边缘计算、分布式云等多种业务部署场景,业内首创单个集群兼容多种计算节点的容器资源管理模式。同时产品作为云原生 Finops 领先布道者,主导开源项目Crane,全面助力客户实现资源优化、成本控制。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档