回溯法 0-1背包问题

回溯法 0-1背包问题一.回溯法回溯法采用的是深度优先策略,回溯法按深度优先策略搜索问题的解空间树。首先从根节点出发搜索解空间树,当算法搜索至解空间树的某一节点时,先利用剪枝函数判断该节点是否可行(即能得到问题的解)。如

大家好,又见面了,我是你们的朋友全栈君。

一.回溯法

回溯法采用的是深度优先策略,回溯法按深度优先策略搜索问题的解空间树。首先从根节点出发搜索解空间树,当算法搜索至解空间树的某一节点时,先利用剪枝函数判断该节点是否可行(即能得到问题的解)。如果不可行,则跳过对该节点为根的子树的搜索,逐层向其祖先节点回溯;否则,进入该子树,继续按深度优先策略搜索。
(1)三个步骤:
    1.针对所给问题,定义问题的解空间;
    2.确定易于搜索的解空间结构;
   3. 以深度优先的方式搜索解空间。
(2)优化方法:
搜索过程使用剪枝函数来为了避免无效的搜索。剪枝函数包括两类:
    1.使用约束函数,剪去不满足约束条件的路径。
    2.使用限界函数,剪去不能得到最优解的路径。

(3)解空间树的类型分为排列树和子集树。

二.0-1背包问题

问题:给定n种物品和一背包。物品i的重量是wi,其价值为pi,背包的容量为C。问应如何选择装入背包的物品,使得装入背包中物品的总价值最大?

 1 #include <iostream>  2 using namespace std;  3  4 #define N 100 //默认有99个物品。第一个不使用  5 int w[N]; //每个物品的重量  6 int v[N]; //每个物品的价值  7 int x[N]; //x[i]=1:物品i放入背包,0代表不放入  8 int n,c; //n:一共有多少物品,c:背包的最大容量  9 10 int CurWeight = 0; //当前放入背包的物品总重量 11 int CurValue = 0; //当前放入背包的物品总价值 12 13 int BestValue = 0; //最优值;当前的最大价值,初始化为0 14 int BestX[N]; //最优解;BestX[i]=1代表物品i放入背包,0代表不放入 15 16 /* 17 *回溯函数 参数t表示当前处在第几层做抉择,t=1时表示当前在决定是否将第一个物品放入背包 18 */ 19 void backtrack(int t) 20 { 21 //叶子节点,输出结果 22 if(t>n) 23  { 24 //如果找到了一个更优的解 25 if(CurValue>BestValue) 26  { 27 //保存更优的值和解 28 BestValue = CurValue; 29 for(int i=1; i<=n; ++i) 30 BestX[i] = x[i]; 31  } 32  } 33 else 34  { 35 //遍历当前节点的子节点:0 不放入背包,1放入背包 36 for(int i=0; i<=1; ++i) 37  { 38 x[t]=i; 39 40 if(i==0) //不放入背包 41  { 42 backtrack(t+1); 43  } 44 else //放入背包 45  { 46 //约束条件:当前物品是否放的下 47 if((CurWeight+w[t])<=c) 48  { 49 CurWeight += w[t]; 50 CurValue += v[t]; 51 backtrack(t+1); 52 CurWeight -= w[t]; 53 CurValue -= v[t]; 54  } 55  } 56  } 57  } 58 } 59 60 int main() 61 { 62 63 cout<<"请输入物品的个数:"<<endl; 64 cin>>n; 65 cout<<"请输入每个物品的重量及价值(如5 4):"<<endl; 66 for(int i = 1; i <= n; i++) 67  { 68 cin>>w[i]>>v[i]; 69  } 70 cout<<"请输入背包的限制容量:"<<endl; 71 cin>>c; 72 73 backtrack(1); 74 75 cout<<"最优值是:"<<BestValue<<endl; 76 cout<<"("; 77 for(int i=1;i<=n;i++) 78 cout<<BestX[i]<<" "; 79 cout<<")"; 80 return 0; 81 }
 1 #include <iostream>  2 using namespace std;  3  4 #define N 100 //默认有99个物品。第一个不使用  5 int w[N]; //每个物品的重量  6 int v[N]; //每个物品的价值  7 int x[N]; //x[i]=1:物品i放入背包,0代表不放入  8 int n,c; //n:一共有多少物品,c:背包的最大容量  9 10 int CurWeight = 0; //当前放入背包的物品总重量 11 int CurValue = 0; //当前放入背包的物品总价值 12 13 int BestValue = 0; //最优值;当前的最大价值,初始化为0 14 int BestX[N]; //最优解;BestX[i]=1代表物品i放入背包,0代表不放入 15 16 void input() 17 { 18 cout<<"请输入物品的个数:"<<endl; 19 cin>>n; 20 cout<<"请输入每个物品的重量及价值(如5 4):"<<endl; 21 for(int i = 1; i <= n; i++) 22  { 23 cin>>w[i]>>v[i]; 24  } 25 cout<<"请输入背包的容量:"<<endl; 26 cin>>c; 27 } 28 void output() 29 { 30 cout<<"最优值是:"<<BestValue<<endl; 31 cout<<"("; 32 for(int i=1;i<=n;i++) 33 cout<<BestX[i]<<" "; 34 cout<<")"; 35 36 } 37 /* 38 *回溯函数 参数t表示当前处在第几层做抉择,t=1时表示当前在决定是否将第一个物品放入背包 39 */ 40 void backtrack(int t,int CurWeight,int CurValue,int rw,int x[]) 41 { 42 //初始调用时rw为所有物品重量和  43 if(t>n) 44  { 45 //如果找到了一个更优的解 46 if(CurWeight==c&&CurValue>BestValue) 47  { 48 //保存更优的值和解 49 BestValue = CurValue; 50 for(int i=1; i<=n; ++i) 51 BestX[i] = x[i]; 52  } 53  } 54 else 55  { 56 //遍历当前节点的子节点:0 不放入背包,1放入背包 57 if(CurWeight+w[t]<=c) //左孩子结点剪枝  58  { 59 x[t]=1;//选取第i个物品回溯  60 backtrack(t+1,CurWeight+w[t],CurValue+v[t],rw-w[t],x); 61  } 62 x[t]=0;//不选取第i个物品回溯  63 if(CurWeight+rw>c)//右孩子结点剪枝  64 backtrack(t+1,CurWeight,CurValue,rw-w[t],x); //rw都减去w[t]代表已经考虑过是否选取当前物品,不必再考虑  65  } 66 67 } 68 69 int main() 70 { 71 72  input(); 73 backtrack(1,0,0,11,x); 74  output(); 75 return 0; 76 }

 <span role="heading" aria-level="2">回溯法 0-1背包问题

<span role="heading" aria-level="2">回溯法 0-1背包问题

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/155436.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 模式的分类

    模式的分类模式的分类

  • [面试题]25个MySQL经典面试题「建议收藏」

    [面试题]25个MySQL经典面试题「建议收藏」经典题目1、MySQL的复制原理以及流程基本原理流程,3个线程以及之间的关联;2、MySQL中myisam与innodb的区别,至少5点2.1问5点不同;2.2innodb引擎的4大特性2.32者selectcount(*)哪个更快,为什么3、MySQL中varchar与char的区别以及varchar(50)中的50代表的涵义3.1varchar与char的区别3.2…

  • Symantec赛门铁克安全软件免密卸载方式[通俗易懂]

    Symantec赛门铁克安全软件免密卸载方式[通俗易懂]装了Symantec后,后面希望卸载他,结果发现卸载需要卸载口令,查了一堆资料,总结有如下几种:1、卸载口令可能是symantec,反正没成本可以简单试试看。不过我是没有通过,这个口令不对我的Symantec。2、使用cleanwipe进行卸载,这是官方的用于卸载Symantec软件的工具。工具很小,应该有版本要求,旧版的不能完成卸载。推荐使用这个方式。我用的是CleanWipe_14.3.558.1000,选中下图中框出来的三个勾,直接下一步即可完成卸载。链接:https://pan.baidu.

  • makefile文件编写「建议收藏」

    makefile文件编写「建议收藏」makefile文件用于管理和组织代码工程的编译和链接,其不是可执行文件,其被make工具解析并完成相关动作,下面笔者将介绍makefile中常用的一些语法说明:1、文件包含:语法:include文件名作用:将其它makefile文件包含进来,组成一个更大的makefile文件,这样有利于makefile模块化编程。通常我们将一些配置选项分开成一个独立的makefile文件,这…

  • JAVA设计模式——适配器模式

    JAVA设计模式——适配器模式适配器模式是一种结构型设计模式。适配器模式的思想是:把一个类的接口变换成客户端所期待的另一种接口,从而使原本因接口不匹配而无法在一起工作的两个类能够在一起工作。用电器来打个比喻:有一个电器的插头是三脚的,而现有的插座是两孔的,要使插头插上插座,我们需要一个插头转换器,这个转换器即是适配器。适配器模式涉及3个角色:源(Adaptee):需要被适配的对象或类型,相当于插头。适配器(Ad

  • MySQL insert or update sql

    MySQL insert or update sqlMySQL一条sql实现数据保存变更  insertorupdate  ,如果没有执行insert,有就update需要有主键 PRIMARY或唯一索引UNIQUEMySQL中的INSERT…ONDUPLICATEKEYUPDATE语句,该语句是基于唯一索引或主键使用ONDUPLICATEKEYUPDATE后面可以放多个字段,用英文逗号分割。使用…

    2022年10月31日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号