C++实现的背包分支和绑定

Question

我正在尝试使用分支和边界来解决这个背包问题的C++实现.这个网站上有一个Java版本:实现分支和绑定背包

我正在努力让我的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");
}

Answer 1

我认为你已将利润和权重值放在错误的向量中.更改:

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.

Answer 2

我相信您要实现的并不是精确的分支和绑定算法。如果我必须将其与某些内容匹配，则它更像是基于估计的回溯。

算法中的问题是您正在使用的数据结构。您要做的只是简单地先推入所有第一级，然后推入所有第二级，然后再将所有第三级推入队列，并按插入顺序将它们取回。您将得到结果，但这只是在整个搜索空间中搜索。

与其按插入顺序弹出元素，您要做的是始终在具有最高估计边界的节点上分支。换句话说，无论它们的估计边界如何，您总是以自己的方式在每个节点上分支。分支定界技术通过每次仅在一个节点上进行分支而获得速度优势，这最有可能导致结果（具有最高的估计值）。

示例：在您的第一次迭代中，假定您找到了两个带有估计值的节点

节点1：110

节点2：80

您正在将它们都推入队列。您的队列变为“ n2-n1头”。在第二次迭代中，您在node1上分支后又推送了两个节点：

节点3：100

节点4：95

并且将它们添加到队列中（“ n4-n3-n2-head”。会出现错误。在下一次迭代中，您将获得的将是node2，但应该是估计的最高的node3值。

因此，如果我不错过您的代码中的某些内容，则您的实现和Java实现都是错误的。您应该使用优先级队列（堆）来实现真实的分支和绑定。