8

分岐と境界を使用して、このナップザックの問題を C++ で実装しようとしています。この Web サイトには 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");
}
4

4 に答える 4

5

利益と重量の値を間違ったベクトルに入れたと思います。変化する：

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 を出力します。

于 2012-07-16T04:45:59.173 に答える
5

あなたが実装しているのは、まさに分岐限定アルゴリズムではないと思います。何かと一致させる必要がある場合は、推定ベースのバックトラッキングに似ています。

アルゴリズムの問​​題は、使用しているデータ構造です。あなたがしていることは、最初にすべての最初のレベルをプッシュし、次にすべての 2 番目のレベルをプッシュし、次にすべての 3 番目のレベルをキューにプッシュして、それらを挿入の順序に戻すことです。結果が得られますが、これは単に検索スペース全体を検索しているだけです。

要素を挿入順序でポップする代わりに、推定境界が最も高いノードで常に分岐する必要があります。言い換えれば、推定された境界に関係なく、常にすべてのノードで分岐しています。ブランチ & バウンド手法は、結果につながる可能性が最も高い (推定値が最も高い) 毎回 1 つのノードのみで分岐することから速度の利点を得ます。

例 : 最初の反復で、推定値を持つ 2 つのノードが見つかったと仮定します。

ノード1 : 110

ノード 2 : 80

両方をキューにプッシュしています。あなたのキューは「n2-n1-head」になりました。

ノード 3 : 100

ノード 4 : 95

そして、それらをキューにも追加しています（「n4-n3-n2-head」。エラーが発生します。次の反復では、取得するのはnode2になりますが、代わりに、推定値が最も高いnode3にする必要があります価値。

したがって、あなたのコードで何かを見逃していなければ、あなたの実装と Java 実装の両方が間違っています。実際のブランチ & バウンドを実装するには、優先キュー (ヒープ) を使用する必要があります。

于 2014-05-23T14:19:27.403 に答える
1

W を 16 に設定しているので、結果は 5 です。ナップザックに入れることができるアイテムは、利益が 5 で重量が 10 のアイテム 3 だけです。

于 2012-07-16T04:51:43.087 に答える