Solving Knapsack using recursive algorithm

Question

So, I am trying to implement this algorithm from our textbook.

I wrote this :

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

Here is the question and output :

It seems like its correct on some places like optimum value, yet isn't fully acceptable. I've tried to debug it, but its quite hard with recursive functions. Can someone please help?

Answer 1

The bottom up solution.

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

You can see that this changes the recursion to a loop, and therefore avoids the global variables. It also makes the code simpler, so that you can avoid checking if the table item is valid (equal to -1 in your example).

The drawback of this solution is, it always traverses all the possible nodes. But it gains better coefficient per item because the recursion and double checking the table item costs more. Both top-down and bottom-up have the same order of complexity O(n^2), and it's hard to tell which one is faster.

Answer 2

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

The problem comes in here. When your table item is greater or equal to 0, you will skip the recursion but still set the table item to 0, which won't be right if your table item is greater than 0.

You only need to update the table item when it needs to be change, so put it in the braces will correct this.