C++ 背包分支定界的C++实现
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/11498035/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
C++ implementation of knapsack branch and bound
提问by user1527877
I am trying to a C++ implementation of this knapsack problem using branch and bounding. There is a Java version on this website here: Implementing branch and bound for knapsack
我正在尝试使用分支和边界来实现这个背包问题的 C++ 实现。这个网站上有一个Java版本：Implementing branch and bound for knapsack
I'm trying to make my C++ version print out the 90 that it should, however it's not doing that, instead, it's printing out 5.
我试图让我的 C++ 版本打印出它应该的 90，但是它没有这样做，而是打印出 5。
Does anyone know where and what the problem may be?
有谁知道问题可能出在哪里？
#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");
}
采纳答案by Bowie Owens
I think you have put the profit and weight values in the wrong vectors. Change:
我认为您将利润和权重值放在错误的向量中。改变：
int p[4] = {2, 5, 10, 5};
int w[4] = {40, 30, 50, 10};
to:
到：
int w[4] = {2, 5, 10, 5};
int p[4] = {40, 30, 50, 10};
and your program will output 90.
你的程序将输出 90。
回答by ralzaul
I believe what you are implementing is not a branch & bound algorithm exactly. It is more like an estimation based backtracking if I have to match it with something.
我相信您正在实施的并不是分支定界算法。如果我必须将它与某些东西相匹配，它更像是基于估计的回溯。
The problem in your algorithm is the data structure that you are using. What you are doing is to simply first push all the first levels, and then to push all second levels, and then to push all third levels to the queue and get them back in their order of insertion. You will get your result but this is simply searching the whole search space.
您算法中的问题是您使用的数据结构。您正在做的是简单地首先推送所有第一级，然后推送所有第二级，然后将所有第三级推送到队列并按照插入顺序将它们放回原处。您将获得结果，但这只是搜索整个搜索空间。
Instead of poping the elements with their insertion order what you need to do is to branch always on the node which has the highest estimated bound. In other words you are always branching on every node in your way regardless of their estimated bounds. Branch & bound technique gets its speed benefit from branching on only one single node each time which is most probable to lead to the result (has the highest estimated value).
您需要做的是始终在具有最高估计界限的节点上进行分支，而不是按其插入顺序弹出元素。换句话说，您总是以自己的方式在每个节点上进行分支，而不管它们的估计边界如何。分支定界技术从每次只在一个节点上分支而获得速度优势，这是最有可能导致结果（具有最高估计值）。
Example : In your first iteration assume that you have found 2 nodes with estimated values
示例：在您的第一次迭代中，假设您找到了 2 个具有估计值的节点
node1: 110
节点 1：110
node2: 80
节点2：80
You are pushing them both to your queue. Your queue became "n2-n1-head" In the second iteration you are pushing two more nodes after branching on node1:
您将它们都推送到您的队列中。你的队列变成了 "n2-n1-head" 在第二次迭代中，你在 node1 上分支后又推送了两个节点：
node3: 100
节点3：100
node4: 95
节点4：95
and you are adding them to you queue as well("n4-n3-n2-head". There comes the error. In the next iteration what you are going to get will be node2 but instead it should be node3 which has the highest estimated value.
并且您也将它们添加到您的队列中（“n4-n3-n2-head”。出现错误。在下一次迭代中，您将获得 node2，但它应该是 node3，它具有最高的估计值价值。
So if I don't miss something in your code both your implementation and the java implementation are wrong. You should rather use a priority queue (heap) to implement a real branch & bound.
因此，如果我没有遗漏您的代码中的某些内容，那么您的实现和 java 实现都是错误的。您应该使用优先级队列（堆）来实现真正的分支定界。
回答by fuse
#include <bits/stdc++.h>
using namespace std;
struct Item
{
float weight;
int value;
};
struct Node
{
int level, profit, bound;
float weight;
};
bool cmp(Item a, Item b)
{
double r1 = (double)a.value / a.weight;
double r2 = (double)b.value / b.weight;
return r1 > r2;
}
int bound(Node u, int n, int W, Item arr[])
{
if (u.weight >= W)
return 0;
int profit_bound = u.profit;
int j = u.level + 1;
int totweight = u.weight;
while ((j < n) && (totweight + arr[j].weight <= W))
{
totweight = totweight + arr[j].weight;
profit_bound = profit_bound + arr[j].value;
j++;
}
if (j < n)
profit_bound = profit_bound + (W - totweight) * arr[j].value /
arr[j].weight;
return profit_bound;
}
int knapsack(int W, Item arr[], int n)
{
sort(arr, arr + n, cmp);
queue<Node> Q;
Node u, v;
u.level = -1;
u.profit = u.weight = 0;
Q.push(u);
int maxProfit = 0;
while (!Q.empty())
{
u = Q.front();
Q.pop();
if (u.level == -1)
v.level = 0;
if (u.level == n-1)
continue;
v.level = u.level + 1;
v.weight = u.weight + arr[v.level].weight;
v.profit = u.profit + arr[v.level].value;
if (v.weight <= W && v.profit > maxProfit)
maxProfit = v.profit;
v.bound = bound(v, n, W, arr);
if (v.bound > maxProfit)
Q.push(v);
v.weight = u.weight;
v.profit = u.profit;
v.bound = bound(v, n, W, arr);
if (v.bound > maxProfit)
Q.push(v);
}
return maxProfit;
}
int main()
{
int W = 55; // Weight of knapsack
Item arr[] = {{10, 60}, {20, 100}, {30, 120}};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum possible profit = "
<< knapsack(W, arr, n);
return 0;
}
**SEE IF THIS HELPS**
回答by perreal
You are setting the W to 16, so the result is 5. The only item you can take into the knapsack is item 3 with profit 5 and weight 10.
您将 W 设置为 16，因此结果为 5。您可以放入背包的唯一物品是利润为 5 且重量为 10 的物品 3。
