天天看點

廣度優先周遊(廣搜)解決01背包問題

搞了好多天才調出來,一個if語句中的關系運算符==和一個寫錯的數組名就困擾了我大半天,可能會有一些不合适的地方,希望大佬們看到可以多多指教。

//廣搜解決01背包問題
#include<iostream>
#include<queue>
using namespace std;
int N, V;
//搜尋樹結點定義
struct Node
{
	int *x = new int[N];
	int v;//目前背包體積
	int m;//目前背包價值
	int k;//目前所屬搜尋到的層數
};
int bestM=0;//背包最高價值
//借用廣搜樹解決01背包問題
void BFS(int N,int V,int v[],int m[])
{
	int i;
	Node Root, Front, lChild, rChild;
	queue<Node>Q;//建立結點順序隊列
	Root.v = 0; Root.m = 0; Root.k = 0;
	for (i = 0; i < N; i++)
		Root.x[i] = 0;
	Q.push(Root);//根結點入隊
	while (!Q.empty())
	{
		Front = Q.front();
		Q.pop();
		//尋找最佳價值
		if (Front.m > bestM)
			bestM = Front.m;
		//擴充搜尋樹結點
		if(Front.k<N)
		{
			if (Front.v + v[Front.k] <= V)//如果把第k件物品裝入不會超過最大容量
			{
				//探測左子樹
				for (i = 0; i < N; i++)
				{
					if (i == Front.k)
						lChild.x[i] = 1;
					else
						lChild.x[i] = Front.x[i];
				}
				lChild.v = Front.v + v[Front.k];//更新目前背包體積
				lChild.m = Front.m + m[Front.k];//更新目前背包價值
				lChild.k = Front.k + 1;//左樹往下一層
				Q.push(lChild);//左孩子入隊
			}
			//總是探測右子樹
			for (i = 0; i < N; i++)
			{
				if (i == Front.k)
					rChild.x[i] = 0;
				else
					rChild.x[i] = Front.x[i];
			}
			rChild.v = Front.v;
			rChild.m = Front.m;
			rChild.k = Front.k + 1;
			Q.push(rChild);
		}
	}
	cout << bestM;
}
//主函數
int main()
{
	//輸入:物品數目N,背包容量V;每個物品的體積v和價值m。
	cin >> N >> V;
	int *v = new int[N];
	int *m = new int[N];
	for (int i = 0; i < N; i++)
		cin >> v[i] >> m[i];
	//廣搜
	BFS(N,V,v,m);
	return 0;
}
           

繼續閱讀