CODEWITHSUNDEEP
c++data-structuresknapsack-problemrecursive-datastructures
Jatin
Jatin

Reputation: 1997

How to find indexes of elements in recursive-knapsack?

I'm trying to implement recursive Knapsack which would return 2 things:

  1. Max value we get by filling knapsack.
  2. Indexes of the elements considered for filling the knapsack.

Please note that I don't want to use Dynamic Programming Approach to get this done (by reverse iterating the 2-D matrix to get the indexes of elements). I want to understand how it can be done in recursive knapsack approach?

This is what I have tried below (getting correct MaxValue (op#1) BUT not getting correct list of indexes (op#2)):

int knapsack(vector<int> wt, vector<int> val, int W, int N, vector<int>& idx)
{
    if (W == 0 || N == 0) return 0;

    if (wt[N - 1] <= W)
    {
        int  consider = val[N - 1] + knapsack(wt, val, W - wt[N - 1], N - 1, idx);
        int  dontconsider = knapsack(wt, val, W, N - 1, idx);

        if (consider > dontconsider)
        {
            idx.push_back(N-1);
        }
        return max(consider, dontconsider);
    }
    else
    {
        return knapsack(wt, val, W, N - 1, idx);
    }
}
int main()
{
    vector<int> wt = { 10, 20, 30 };
    vector<int> val = { 60, 100, 120 };
    int W = 50;

    vector<int> idx; // this should retain the indexes of the elements considered for knapsack.
    cout << knapsack(wt, val, W, wt.size(), idx);
    cout << "\nIndex of elements considered for knapsack: ";
    for (int i = 0; i < idx.size(); i++)
        cout << idx[i] << " ";

    getchar();
    return 0;
}

Expected output should be:

220

Index of elements considered for knapsack: 1 2

Please help me. Thank you.

Upvotes: 1

Views: 453

Answers (2)

AQTS
AQTS

Reputation: 104

Damien's diagnostic is correct. The problem is the repetition of already considered entries in the idx vector in the multiple evaluated branches of the iterations.

I would only add a new approach which I think would be more simple. Instead of using a vector, you can simply change your code making idx a set object, which is a container like a vector, but with one important difference: it does not allow repeated elements. So, if you insert an element already contained in a set, it will not add a new one.

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

int knapsack(const vector<int> wt, const vector<int> val, const int W, int N, set<int>& idx)
{
    if (W == 0 || N == 0) return 0;

    if (wt[N - 1] <= W)
    {
        int  consider = val[N - 1] + knapsack(wt, val, W - wt[N - 1], N - 1, idx);
        int  dontconsider = knapsack(wt, val, W, N - 1, idx);

        if (consider > dontconsider)
        {
            idx.insert(N-1);
        }
        return max(consider, dontconsider);
    }
    else
    {
        return knapsack(wt, val, W, N - 1, idx);
    }
}
int main()
{
    vector<int> wt = { 10, 20, 30 };
    vector<int> val = { 60, 100, 120 };
    int W = 50;

    set<int> idx; // this should retain the indexes of the elements considered for knapsack.
    cout << "Maximum value obtained: " << knapsack(wt, val, W, wt.size(), idx);

    cout << "\nIndex of elements considered for knapsack: ";
    for (auto i : idx)
        cout << i << " ";
    cout << endl;

    getchar();
    return 0;
}

Here is my example code using a set (note I had to make small adjustments, since there are some methods like pusk_back that are vector specific):

Upvotes: 0

Damien
Damien

Reputation: 4864

The vector idx is passed by reference: vector<int>& idx.

The issue is that here:

int  consider = val[N - 1] + knapsack(wt, val, W - wt[N - 1], N - 1, idx);
int  dontconsider = knapsack(wt, val, W, N - 1, idx);

This vector idx is modified twice.

One solution is to create a temporary vector for the first call...

#include <iostream>
#include <vector>
#include <algorithm>

int knapsack(const std::vector<int>& wt, const std::vector<int>& val, int W, int N, std::vector<int>& idx) {
    if (W == 0 || N == 0) return 0;

    if (wt[N - 1] <= W) {
        std::vector<int> idx0;
        int  consider = val[N - 1] + knapsack(wt, val, W - wt[N - 1], N - 1, idx0);
        int  dontconsider = knapsack(wt, val, W, N - 1, idx);

        if (consider > dontconsider) {
            idx = idx0;
            idx.push_back(N-1);
            return consider;
        }
        return dontconsider;
    }
    else {
        return knapsack(wt, val, W, N - 1, idx);
    }
}
int main()
{
    std::vector<int> wt = { 10, 20, 30 };
    std::vector<int> val = { 60, 100, 120 };
    int W = 50;

    std::vector<int> idx; // this should retain the indexes of the elements considered for knapsack.
    std::cout << knapsack(wt, val, W, wt.size(), idx);
    std::
    cout << "\nIndex of elements considered for knapsack: ";
    for (int i = 0; i < idx.size(); i++)
        std::cout << idx[i] << " ";
    std::cout << "\n";
    //getchar();
    return 0;
}

Upvotes: 1

Related Questions