使用递归算法求解背包

Question

所以，我正在尝试从我们的课本中实现这个算法。

我写了这个：

// Knapsack_memoryfunc.cpp : Defines the entry point for the console application.
//Solving Knapsack problem using dynamic programmig and Memory function

#include "stdafx.h"
#include "iostream"
#include "iomanip"
using namespace std;

int table[20][20] = { 0 };
int value, n, wt[20], val[20], max_wt;

// ---CONCERNED FUNCTION-----

int MNSack(int i, int j)
{
    value = 0;
    if (table[i][j] < 0)
        if (j < wt[i])
            value = MNSack(i - 1, j);
        else
            value = fmax(MNSack(i - 1, j), val[i] + MNSack(i - 1, j - wt[i]));

    table[i][j] = value;
    return table[i][j];
}

// --------------------------

void items_picked(int n, int max_wt)
{
    cout << "\n Items picked : " << endl;
    while (n > 0)
    {
        if (table[n][max_wt] == table[n - 1][max_wt])   // if value doesnot change in table column-wise, item isn't selected
            n--;                                        // n-- goes to next item
        else                                            // if it changes, it is selected
        {
            cout << " Item " << n << endl;
            max_wt -= wt[n];                            // removing weight from total available (max_wt)
            n--;                                        // next item
        }
    }
}

int main()
{

    cout << " Enter the number of items : ";
    cin >> n;
    cout << " Enter the Maximum weight : ";
    cin >> max_wt;
    cout << endl;
    for (int i = 1; i <= n; i++)
    {
        cout << " Enter weight and value of item " << i << " : ";
        cin >> wt[i] >> val[i];
    }

    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= max_wt; j++)
            table[i][j] = 0;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= max_wt; j++)
            table[i][j] = -1;

    cout << " Optimum value : " << MNSack(n, max_wt);

    cout << " \n Table : \n";
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= max_wt; j++)
            if (table[i][j] == -1)
                cout << setw(5) << "-";
            else
                cout << setw(5) << table[i][j];
        cout << endl;
    }

    items_picked(n, max_wt);


    return 0;
}

这是问题和输出：

它在某些地方似乎是正确的，例如最佳值，但并不完全可以接受。我试过调试它，但是使用递归函数很难。有人可以帮忙吗？

Answer 1

int MNSack(int i, int j)
{
    value = 0;
    if (table[i][j] < 0)
    {
        if (j < wt[i])
            value = MNSack(i - 1, j);
        else
            value = max(MNSack(i - 1, j), val[i] + MNSack(i - 1, j - wt[i]));

        table[i][j] = value;
    }
    return table[i][j];
}

问题就出在这里。当您的 table 项大于或等于 0 时，您将跳过递归但仍将 table 项设置为 0，如果您的 table 项大于0.

您只需要在 table 项目需要更改时更新它，所以将其放在大括号中将更正此问题。

Answer 2

自下而上的解决方案。

#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;


int main()
{
    int table[20][20] = { 0 };
    int value, n, wt[20], val[20], max_wt;

    cout << " Enter the number of items : ";
    cin >> n;
    cout << " Enter the Maximum weight : ";
    cin >> max_wt;
    cout << endl;
    for (int i = 1; i <= n; i++)
    {
        cout << " Enter weight and value of item " << i << " : ";
        cin >> wt[i] >> val[i];
    }

    // Initialization
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= max_wt; j++)
            table[i][j] = 0;

    // In practice, this can be skipped in a bottom up solution
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= max_wt; j++)
            table[i][j] = -1;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= max_wt; j++)
        {
            if (j < wt[i])
                table[i][j] = table[i - 1][j];
            else
                table[i][j] = max(table[i - 1][j], val[i] + table[i - 1][j - wt[i]]);
        }
    }

    cout << " Optimum value : " << table[n][max_wt] << endl;

    cout << " \n Table : \n";
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= max_wt; j++)
            if (table[i][j] == -1)
                cout << setw(5) << "-";
            else
                cout << setw(5) << table[i][j];
        cout << endl;
    }

    return 0;
}

您可以看到这将递归更改为循环，因此避免了全局变量。它还使代码更简单，这样您就可以避免检查 table 项是否有效（在您的示例中等于 -1）。

这个解决方案的缺点是，它总是遍历所有可能的节点。但是它获得了每个项目更好的系数，因为递归和双重检查 table 项目成本更高。自上而下和自下而上的复杂度都是O(n^2)，很难说哪个更快。

使用递归算法求解背包

Solving Knapsack using recursive algorithm

c++

algorithm

recursion

knapsack-problem