分支限界法求解0/1背包问题_分支定界解决01背包matlab代码

分支限界法求解0/1背包问题

提示：这里可以添加系列文章的所有文章的目录，目录需要自己手动添加

---

提示：写完文章后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

提示：这里可以添加本文要记录的大概内容：
分支限界法求解0/1背包问题基本原理推荐视频观看，通俗易懂。

https://www.bilibili.com/video/BV1gb411G7FH?spm_id_from=333.337.search-card.all.click

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、准备工作

1/基于贪心思想，按照性价比由高到低（单个背包价值/单个背包重量）对物品进行排序，需要用到sort()函数。
2/几个方案中预期价值最高的方案是我们的研究方向，采用大根堆(priority_queue)进行排序。

二、使用步骤

1.引入库

代码如下（示例）：

#include<iostream>
#include<queue>
1
2

2.代码

代码如下（完整）：

using namespace std;
//分支限界发求解01背包问题 基于的是贪心思想   在第1个物品放入 和没放入背包时  其实 都有一个理论上可能达到的最大价值 
//我们选理论价值最大的那个可能性   如果该物品放入背包 可能的价值大  我们就走这条路 如果这个不放入 价值大 我们就走另外一条路 
//总容量
int totalvolume ;
//物品数量
int amount;

//递增系数
int id_add=0;
//定义一个结构
struct element
{
	//编号
	int Id;
	//重量
	int Weight;
	// 价值
	int Worth;
	element()
	{
		Id = id_add++;
		Weight = 0;
		Worth = 0;
	}
} ;
//保存某个方案 
struct PLAN
{
	//每个方案都会保存一个数组 （每个物品 是否放入）
	bool isIn[11] = {0};
	// 已经存入的物品的价值
	double alreadyWorth;
	//可能最大利益
	double  mostWorth;
	//剩余容量
	int leftVolume;
	//第Id个物品是否放入  这表示前Id-1个物品 是否放入都已经确定了
	int Id;
	PLAN()
	{
	}
	//初始化 所有物品都没放入的初始状态
	void Init(element* Array)
	{
		alreadyWorth = 0;
		mostWorth = 0;
		leftVolume = totalvolume;
		Id = 0;
		calculate(Array);
	};
	//后序所有的初始化都采用这个  都是在前面基础上 判断第n个物品是否放入  放入是1  不放入是0 
	void Init(PLAN& a, int is_in, element* Array)
	{

		std::copy(a.isIn, a.isIn + amount, isIn);
		//不放入
		Id = a.Id;
		leftVolume = a.leftVolume;
		alreadyWorth = a.alreadyWorth;
		//放入
		if (is_in == 1 && leftVolume - Array[Id].Weight >= 0)
		{
			leftVolume -= Array[Id].Weight;
			alreadyWorth += Array[Id].Worth;
			isIn[Id] = 1;
		}
		Id++;
		calculate(Array);
	};
	//计算某个方案的 mostWorth
	void  calculate(element*Array)
	{
		int id_used = Id;
		int leftVolume1 = leftVolume;
		mostWorth = alreadyWorth;
		while (id_used <= amount-1&&leftVolume1 - Array[id_used].Weight>= 0)
		{
			leftVolume1 -= Array[id_used].Weight;
			mostWorth += Array[id_used].Worth;
			id_used++;
		}
		if (leftVolume1 > 0 && id_used <= amount-1)
		{
			mostWorth += leftVolume1 * ((double)Array[id_used].Worth /(double) Array[id_used].Weight);
		}	
	}

	
};
bool operator<(const PLAN& a,const PLAN& b)
{
	return a.mostWorth < b.mostWorth;
}
bool operator>(const PLAN& a, const PLAN& b)
{
	return a.mostWorth > b.mostWorth;
}
bool operator>=(const PLAN& a, const PLAN& b)
{
	return a.mostWorth >= b.mostWorth;
}
ostream& operator<<(ostream& os, const PLAN&a)
{
	for (int i = 0; i <= 10; i++)
	{
		if (a.isIn[i] == 1)
		{
			os << i+1 <<" ";
		}
	}
	os <<"最优方案价值为"<<a.alreadyWorth<<endl;
	return os;
}
bool cmp_element(element&a, element&b)
{
	return ((double)a.Worth / a.Weight) > ((double)b.Worth / b.Weight);
}
int main()
{
	srand((unsigned)time(NULL));
	//大根堆
	priority_queue<PLAN>mHeap;


	cout << "请输入总的容量" << endl;
	cin >> totalvolume;
	cout << "输入物品数量" << endl;
	cin >> amount;
	element* Item = new element[amount];
	for (int i = 0; i < amount; i++)
	{
		cout << "输入第" << i + 1 << "组物品的重量和价值。以空格隔开" << endl;
		cin >> Item[i].Weight >> Item[i].Worth;

    } 
	//按性价比排序
	 std::sort(Item, Item +amount, cmp_element);
	 cout << " 排序之后：" << endl;
	 for (int i = 0; i < amount; i++)
	 {
		 cout << i + 1 << " " << Item[i].Weight << " " << Item[i].Worth << endl;
	 }
	//临时方案
	PLAN tempPlan;
	tempPlan.Init(Item);
	//临时方案
	PLAN tempPlan1;
	while (tempPlan.Id !=amount)
	{
		//第n个物品放入
		tempPlan1.Init(tempPlan, 0, Item);
		mHeap.push(tempPlan1);
		//第n个物品不放入
		tempPlan1.Init(tempPlan, 1, Item);
		mHeap.push(tempPlan1);
		tempPlan = mHeap.top();
		mHeap.pop();
	}
	//循环结束的方案 即为最优方案  因为到达叶子节点
	cout << tempPlan;
	system("pause");
	delete[]Item;
	return 0;
}

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166

该处使用的url网络请求的数据。

---

总结

提示：这里对文章进行总结：

主要目的是加深学习印象，由于是自学，很多地方处理的不是那么简练，欢迎批评指正。