搞了好多天才調出來,一個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;
}