回溯法 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)


相关推荐

  • hadoop hdfs命令_hadooplinux命令

    hadoop hdfs命令_hadooplinux命令概述所有的HDFS命令都调用bin/hdfs脚本文件,如果运行hdfs脚本没有带任何参数的话,则打印所有命令的描述。 使用:hdfs[SHELL_OPTIONS]COMMAND[GENERIC_OPTIONS][COMMAND_OPTIONS]Hadoop是一个参数解析框架,采用解析泛型选项以及运行类。命令参数 描述 –config–loglevel …

  • string转JSONObject遍历多层找到key的value

    string转JSONObject遍历多层找到key的value先上代码packagecom.zhph;/***@Description:*@Author:xuhaibo*@Date:${Date}*@ModifiedBy:*/importnet.sf.json.JSONArray;importnet.sf.json.JSONObject;importjava.util.Iterator;/****@compa

  • java dom4j 查找_java dom4j根据条件读取查找xml节点的方法

    java dom4j 查找_java dom4j根据条件读取查找xml节点的方法1.假如有下面的books.xml要用javadom4j解析查找。LuceneStudingDom4jTutorialsSpringinActionO’Reilly2.下面我们使用dom4j的xPath来解析:publicvoidparseBooks(){SAXReaderreader=newSAXReader();try{Documentdoc=reader.rea…

  • wxPython的基础教程

    wxPython的基础教程写在前面的话:上个假期学习了Python,发现它真的是一门很有趣的语言,所以这学期想学一些python的可视化编程,于是选择了wxPython。但是我在网上找中文教程找了好久都没有找到中文的教程(额,也许是我方法不对),无奈只好看英文的啦。于是在这个网站上看完了wxPython的基础教程,但是为了方便广大网友所以决定将这个网页中的内容翻译过来。花费了3个晚上的时间,终于把它翻译完了。但是我只是一个

  • 粒子群算法matlab代码(注释很详细哦,图像也美美哒,任意维度)[通俗易懂]

    粒子群算法matlab代码(注释很详细哦,图像也美美哒,任意维度)[通俗易懂]整个程序分为5个脚本pso1_mian.m:主程序,在此脚本内设置参数。pso1_im.m:画出函数图像(仅1维和2维)pso1_in.m:初始化pso1_in2.m:迭代寻优并输出结果另外还有一个目标函数,单独为一个脚本。推荐的测试函数—>这里先上运行结果图下面是源码1.pso1_mian.m这里的目标函数用函数句柄的形式调用(第15行)%%粒子群算法%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%pso1_im

  • java调用Oracle分页存储过程

    Java程序–创建游标包–存储过程推荐:http://www.cnblogs.com/roucheng/p/3504465.html

    2021年12月27日

发表回复

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

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