首页 > 代码库 > 回溯法解背包问题分析
回溯法解背包问题分析
先亮出题目:
一,背包问题 及 回溯法解其问题的伪代码
二,赋值后的具体实例
三,如何看懂伪代码
(1)真正了解回溯法的核心思想
我总结的回溯法解题步骤:
<1>先找出第一个解
<2>回溯
(2)回溯法核心思想 + 伪代码 + 图9-5 树结构来分析
四,伪代码代入值解析
核心:先找到第一个解,再回溯。
cw=0;//背包当前重量 初始值
cp=0;//背包当前价值 初始值
k=1;//第一个物品
n=8;//共8个物品
W=110
第一步:得出第1个可行解:
(1)k=1
k=1 <=8 and 0+1<110 //如果把第1个物品放入背包中,背包中物品重量1<背包容量110 可放入
cw=0+1=1; //把第1个物品放入背包后,目前背包重量=1
cp=0+11=11; //把第1个物品放入背包后,目前背包价值=11
Y[1]=1; //第1个物品放入背包中,则给Y[1]赋值为1
K=1+1=2; //尝试放第2个物品
(2)k=2
K=2 <=8 and 1+11<110 //如果再把第2个物品放入背包中,背包中物品重量12<背包容量110 可放入
cw=1+11=12; //把第2个物品放入背包后,目前背包重量=12
cp=11+21=32; //把第2个物品放入背包后,目前背包价值=32
Y[2]=1; //第2个物品放入背包中,则给Y[2]赋值为1
K=2+1=3; //尝试放第3个物品
(3)k=3
K=3 <=8 and 12+21=33<110 //如果把第3个物品放入背包中,背包中物品重量33<背包容量110 可放入
cw=12+21=33; //把第3个物品放入背包后,目前背包重量=33
cp=32+31=63; //把第3个物品放入背包后,目前背包价值=63
Y[3]=1; //第3个物品放入背包中,则给Y[3]赋值为1
K=3+1; //尝试放第4个物品
(4)k=4
K=4<8 and 33+23=56 //如果把第4个物品放入背包中,背包中物品重量 56<背包容量110 可放入
cw=33+23=56; //把第4个物品放入背包后,目前背包重量=56
cp=63+33=96; //把第4个物品放入背包后,目前背包价值=96
Y[4]=1; //第4个物品放入背包中,则给Y[4]赋值为1
K=4+1; //尝试放第5个物品
(5)k=5
K=5 <=8 and 56+33=89<110 //如果把第5个物品放入背包中,背包中物品重量89<背包容量110 可放入
cw=56+33=89; //把第5个物品放入背包中,目前背包重量=86
cp=96+43=139; //把第 5 个物品放入背包中,目前背包价值=139
Y[5]=1; //第5个物品放入背包中,则给Y[5]赋值为1
K=5+1; //尝试放第6个物品
(6)k=6
K=6 <=8 and 89+43=132>110 //如果把第6个物品放入背包中,背包中物品重量132>背包容量110 不可放入
Y[6]=0; //第6个物品不能放入背包中,则给Y[6]赋值为0
BOUND(139,89,6,110)=139 > fp=-1
K=6+1=7
(7)k=7 <= 8 and 89+45 > 110 //如果把第7个物品放入背包中,背包中物品重量 134 > 背包容量110 不可放入
Y[7]=0; //第7个物品不能放入背包中,则给Y[7]赋值为0
BOUND(139,89,7,110)=139 > fp=-1
K=7+1
(8)k=8 <=8 and 89+55>110 //如果把第8个物品放入背包中,背包中物品重量 144 > 背包容量110 不可放入
Y[8]=0; //第8个物品不能放入背包中,则给Y[8]赋值为0
BOUND(139,89,8,110)=139 > fp=-1
K=8+1
(9)k=9 >n=8
Fp=cp=139;
Fw=cw=89;
K=8;
X=[1,1,1,1,1,0,0,0];
输出第1个可行解X=[1,1,1,1,1,0,0,0]
第二步:回溯 得出第2个解
此时k=8
BOUND(139,89,8,110)=139 <= fp=139 //前8个物品分别已经确定了是否放入
k=8-1
k=7 != 0 and Y[7]!=1
k=7-1
k=6!=0 and Y[6]!=1
k=6-1
k=6!=0 and Y[5]=1
Y[5]=0
cw=89-33=56
cp=139-43=96
BOUND(96,56,5,110)=149 >= fp=139 //前5个物品分别已经确定了是否放入 1,1,1,1,0 计算后3个物品是否放入
K=5+1
K=6 <=8 and 56+43=99<=110
cw=56+43=99
cp=96+53=149
Y[k]=1
K=6+1
K=7 <= 8 and 99+45 > 110
Y[7]=0
BOUND(149,99,7,110)=149 > fp=139
K=7+1
K=8 <=8 and 99+55>110
Y[8]=0
BOUND(149,99,8,110)=149 > fp=139
K=8+1
K=9>8
Fp=cp=149
Fw=cw=99
K=8
X=Y=[1,1,1,1,0,1,0,0]
输出第2个可行解X= [1,1,1,1,0,1,0,0]
………继续回溯得到第3个解
………………………….第4个解
…………………………..
五,总结
文字语言表达能力差,但自认为回溯法的背包问题已经研究通了。对于算法相当薄弱的我,突然对这部分有了较大兴趣,近几天在研究其他算法,略懂皮毛。有意者可面对面交流。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。