0-1背包回溯算法【适合小白，带分析+注释】

121 阅读 0 评论 80 点赞

我是靠谱客的博主刻苦月光，这篇文章主要介绍0-1背包回溯算法【适合小白，带分析+注释】，现在分享给大家，希望可以做个参考。

0-1背包回溯算法【适合小白，带分析+注释】

题目：用回溯算法实现0-1背包，背包的容积为7
装4件物品，物品的价值分别9,10,7,4，物品的重量分别是3,5,2,1，请用回溯法实现背包所能装入的最大价值？

分析：
所谓0-1背包，为了最大的价值，考虑当前物品装或者不装【只有这两种情况，而背包问题可以只装物品的部分】，解空间可以用子集数来表示。
解0-1背包问题的回溯法，与装载问题的回溯法类似，搜索解空间树时，只要左孩子结点是一个可行结点，搜索就进入左子树，而只有在右子树包含更优解时才进入右子树，否则就把右子树剪掉。
这就是问题的关键，怎么把右子树剪掉：我们可以设计一个上界函数，只有当上界函数返回的值大于当前最优值，才进入右子树（也就是说，当前这个物品我不装，而去装下一个物品，得到的价值更大）
上界函数：将物品按单位重量价值降序排列，依次取物品装入【这是为了得到一个上界值，其实本身是不能取到的，所以当物品放不下，我们可以取部分装，这就类似背包问题】
所以物品的价值，重量，单位价值属性用结构体存储，本方法大部分处理时间在这个，其实回溯很简单，主要是为了oj提交，直接根据题目所给的数据进行编程，如果只是想练习回溯，可以自己事前计算好物品的单位重量价值，然后将价值数组，重量数组也按物品的单位重量价值降序排列

复制代码

//1右子树可能包含最优解才进入右子树 否则将右子树减去
//2设置r是当前剩余价值总和 cp是当前价值 bestp当前最优价值
//3上界函数 将物品但单位价值降序排列 按背包问题(可以装部分) 计算出上界值
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
#define N 4
struct node{//建立节点数组
int p;//价值
int w;//重量
double per;//平均价值
}s[N];
int P[4]={9,10,7,4};//物品的价值
int W[4]={3,5,2,1};//物品的重量
double Per[4];
int c=7;//背包的容量
int cw;//当前重量
int cp;//当前价值
int bestp=0;//当前最优价值
//交换函数
void swap(int i,int j){//结构体存储数据 所以不能直接交换 只能将每个属性逐一交换
int a,b;
double c;
a=s[i].p;
s[i].p=s[j].p;
s[j].p=a;
b=s[i].w;
s[i].w=s[j].w;
s[j].w=b;
c=s[i].per;
s[i].per=s[j].per;
s[j].per=c;
}
void f(){//计算物品的平均重量价值
for(int i=0;i<N;i++){
s[i].p=P[i];
s[i].w=W[i];
s[i].per=P[i]*1.0/W[i];
}
}
void sort(){//冒泡排序
for(int i=0;i<N;i++){
for(int j=0;j<N-i;j++){
if(s[j].per<s[j+1].per){
swap(j,j+1);
}
}
}
}
int Bound(int i){//计算上界的函数
int cleft=c-cw;//剩余容量
int b=cp;//存储当前价值
while(i<N&&s[i].w<cleft){
cleft-=s[i].w;
b+=s[i].p;
}
if(i<N){
b+=s[i].p*(cleft/s[i].w);
}
}
void dfs(int i){//核心回溯算法
if(i>N){
bestp=cp;
return;
}
if(cw+s[i].w<c){
//小于背包的容量说明可以继续装
cw+=s[i].w;
cp+=s[i].p;
dfs(i+1);
cw-=s[i].w;
cp-=s[i].p;
}
if(Bound(i+1)>bestp){
//加上下一个价值比当前值更大 也就是说不装当前这个 装下一个可能价值更好
dfs(i+1);
}
}
void display(){//展示输出函数 可以不要用 只是为了将数据输出检测是否正确
for(int i=0;i<N;i++){
cout<<"p"<<s[i].p<<endl;
cout<<"w"<<s[i].w<<endl;
cout<<"per"<<s[i].per<<endl;
}
}
int main(){
f();
//	cout<<"排序前"<<endl;
//	display();
//	sort();
//	cout<<"排序后"<<endl;
//	display();
//	cout<<"jk"<<endl;
dfs(0);
cout<<"最优值为："<<bestp<<endl;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
//1右子树可能包含最优解才进入右子树 否则将右子树减去
//2设置r是当前剩余价值总和 cp是当前价值 bestp当前最优价值
//3上界函数 将物品但单位价值降序排列 按背包问题(可以装部分) 计算出上界值
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
#define N 4
struct node{//建立节点数组
int p;//价值
int w;//重量
double per;//平均价值
}s[N];
int P[4]={9,10,7,4};//物品的价值
int W[4]={3,5,2,1};//物品的重量
double Per[4];
int c=7;//背包的容量
int cw;//当前重量
int cp;//当前价值
int bestp=0;//当前最优价值
//交换函数
void swap(int i,int j){//结构体存储数据 所以不能直接交换 只能将每个属性逐一交换
int a,b;
double c;
a=s[i].p;
s[i].p=s[j].p;
s[j].p=a;
b=s[i].w;
s[i].w=s[j].w;
s[j].w=b;
c=s[i].per;
s[i].per=s[j].per;
s[j].per=c;
}
void f(){//计算物品的平均重量价值
for(int i=0;i<N;i++){
s[i].p=P[i];
s[i].w=W[i];
s[i].per=P[i]*1.0/W[i];
}
}
void sort(){//冒泡排序
for(int i=0;i<N;i++){
for(int j=0;j<N-i;j++){
if(s[j].per<s[j+1].per){
swap(j,j+1);
}
}
}
}
int Bound(int i){//计算上界的函数
int cleft=c-cw;//剩余容量
int b=cp;//存储当前价值
while(i<N&&s[i].w<cleft){
cleft-=s[i].w;
b+=s[i].p;
}
if(i<N){
b+=s[i].p*(cleft/s[i].w);
}
}
void dfs(int i){//核心回溯算法
if(i>N){
bestp=cp;
return;
}
if(cw+s[i].w<c){
//小于背包的容量说明可以继续装
cw+=s[i].w;
cp+=s[i].p;
dfs(i+1);
cw-=s[i].w;
cp-=s[i].p;
}
if(Bound(i+1)>bestp){
//加上下一个价值比当前值更大 也就是说不装当前这个 装下一个可能价值更好
dfs(i+1);
}
}
void display(){//展示输出函数 可以不要用 只是为了将数据输出检测是否正确
for(int i=0;i<N;i++){
cout<<"p"<<s[i].p<<endl;
cout<<"w"<<s[i].w<<endl;
cout<<"per"<<s[i].per<<endl;
}
}
int main(){
f();
//	cout<<"排序前"<<endl;
//	display();
//	sort();
//	cout<<"排序后"<<endl;
//	display();
//	cout<<"jk"<<endl;
dfs(0);
cout<<"最优值为："<<bestp<<endl;
}