c++ - 使用递归算法求解背包

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

问题就在这里。当您的表项大于或等于 0 时，您将跳过递归，但仍将表项设置为 0，如果您的表项大于 0，则不正确。

你只需要在需要改变的时候更新表项，所以把它放在大括号里会纠正这个问题。