gpt4 book ai didi

背包分支定界的C++实现

转载 作者:可可西里 更新时间:2023-11-01 17:38:19 30 4
gpt4 key购买 nike

我正在尝试使用分支定界的 C++ 实现这个背包问题。此网站上有一个 Java 版本:Implementing branch and bound for knapsack

我试图让我的 C++ 版本打印出它应该打印出的 90,但它并没有这样做,而是打印出 5。

有谁知道问题出在哪里?

#include <queue>
#include <iostream>
using namespace std;

struct node
{
int level;
int profit;
int weight;
int bound;
};

int bound(node u, int n, int W, vector<int> pVa, vector<int> wVa)
{
int j = 0, k = 0;
int totweight = 0;
int result = 0;

if (u.weight >= W)
{
return 0;
}
else
{
result = u.profit;
j = u.level + 1;
totweight = u.weight;

while ((j < n) && (totweight + wVa[j] <= W))
{
totweight = totweight + wVa[j];
result = result + pVa[j];
j++;
}

k = j;

if (k < n)
{
result = result + (W - totweight) * pVa[k]/wVa[k];
}
return result;
}
}

int knapsack(int n, int p[], int w[], int W)
{
queue<node> Q;
node u, v;
vector<int> pV;
vector<int> wV;
Q.empty();

for (int i = 0; i < n; i++)
{
pV.push_back(p[i]);
wV.push_back(w[i]);
}

v.level = -1;
v.profit = 0;
v.weight = 0;

int maxProfit = 0;

//v.bound = bound(v, n, W, pV, wV);
Q.push(v);

while (!Q.empty())
{
v = Q.front();
Q.pop();

if (v.level == -1)
{
u.level = 0;
}
else if (v.level != (n - 1))
{
u.level = v.level + 1;
}

u.weight = v.weight + w[u.level];
u.profit = v.profit + p[u.level];

u.bound = bound(u, n, W, pV, wV);

if (u.weight <= W && u.profit > maxProfit)
{
maxProfit = u.profit;
}

if (u.bound > maxProfit)
{
Q.push(u);
}

u.weight = v.weight;
u.profit = v.profit;

u.bound = bound(u, n, W, pV, wV);

if (u.bound > maxProfit)
{
Q.push(u);
}
}
return maxProfit;
}

int main()
{
int maxProfit;
int n = 4;
int W = 16;
int p[4] = {2, 5, 10, 5};
int w[4] = {40, 30, 50, 10};

cout << knapsack(n, p, w, W) << endl;

system("PAUSE");
}

最佳答案

我认为您将利润和权重值放在了错误的 vector 中。变化:

int p[4] = {2, 5, 10, 5};
int w[4] = {40, 30, 50, 10};

到:

int w[4] = {2, 5, 10, 5};
int p[4] = {40, 30, 50, 10};

你的程序将输出 90。

关于背包分支定界的C++实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11498035/

30 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com