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");
}

person user1527877    schedule 16.07.2012    source источник
comment
Пожалуйста, не редактируйте свой вопрос после того, как он решен.   -  person Xeo    schedule 16.07.2012


Ответы (3)


Я думаю, что вы поместили значения прибыли и веса в неправильные векторы. Изменять:

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};

и ваша программа выведет 90.

person Bowie Owens    schedule 16.07.2012

Я считаю, что то, что вы реализуете, не является алгоритмом ветвей и границ. Это больше похоже на откат, основанный на оценке, если мне нужно сопоставить его с чем-то.

Проблема в вашем алгоритме заключается в структуре данных, которую вы используете. То, что вы делаете, это просто сначала поместить все первые уровни, затем поместить все вторые уровни, а затем поместить все третьи уровни в очередь и вернуть их в порядке вставки. Вы получите свой результат, но это просто поиск по всему пространству поиска.

Вместо того, чтобы выталкивать элементы с их порядком вставки, вам нужно всегда переходить к узлу, который имеет наивысшую оценку. Другими словами, вы всегда разветвляетесь на каждом узле на своем пути, независимо от их предполагаемых границ. Метод ветвей и границ получает преимущество в скорости за счет ветвления только на одном узле каждый раз, который с наибольшей вероятностью приведет к результату (имеет наибольшее оценочное значение).

Пример. В первой итерации предположим, что вы нашли 2 узла с оценочными значениями.

узел 1: 110

узел 2: 80

Вы подталкиваете их обоих к своей очереди. Ваша очередь стала «n2-n1-head». Во второй итерации вы добавляете еще два узла после ветвления на node1:

узел 3: 100

узел 4: 95

и вы также добавляете их в свою очередь («n4-n3-n2-head». Возникает ошибка. На следующей итерации вы получите узел2, но вместо этого он должен быть узлом3, который имеет самую высокую оценку ценность.

Поэтому, если я ничего не пропущу в вашем коде, и ваша реализация, и реализация Java неверны. Вам лучше использовать приоритетную очередь (кучу) для реализации реальной ветки и привязки.

person ralzaul    schedule 23.05.2014

Вы устанавливаете W на 16, поэтому результат равен 5. Единственный предмет, который вы можете взять в рюкзак, — это предмет 3 с прибылью 5 и весом 10.

person perreal    schedule 16.07.2012