分支限界法求解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>

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;
}

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

总结


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


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