Python to C++: Algorithm that list all combinations of Knapsack using recursion

Question

I'm trying to implement a code that lists all possible combinations of a Knapsack problem using recursion. I have difficulty with recursion. I tried to solve it and got nothing, so I did some research and I found a code in Java Python, but I'm having a hard time trying to rewrite that code in C++.

Here is the solution code, in Java Python:

items = [1,1,3,4,5]
knapsack = []
limit = 7

def print_solutions(current_item, knapsack, current_sum):
    #if all items have been processed print the solution and return:
    if current_item == len(items):
        print knapsack
        return

    #don't take the current item and go check others
    print_solutions(current_item + 1, list(knapsack), current_sum)

    #take the current item if the value doesn't exceed the limit
    if (current_sum + items[current_item] <= limit):
        knapsack.append(items[current_item])
        current_sum += items[current_item]
        #current item taken go check others
        print_solutions(current_item + 1, knapsack, current_sum )

print_solutions(0,knapsack,0)

I found that code in this link

Here is what I tried to do..

#include <iostream>
using namespace std;   

void AddItem(int item, int *knapsack) {
    int i = 0;
    while (knapsack[i] != -1)
        i++;    
    knapsack[i] = item;

};
void printKnapsack(int *knapsack, int n) {
    cout << "[";
    for (int i = 0; i < n; i++)
        if (knapsack[i] != -1)
            cout << knapsack[i] << ",";
}

void print_solutions(int current_item, int *knapsack, int current_sum, int *items, int n, int limit) {
    //if all items have been processed print the solution and return
    if (current_item == n - 1) {
        printKnapsack(knapsack, n);
        return;
    };

    //don't take the current item and go check others
    print_solutions(current_item + 1, knapsack, current_sum, items, n, limit);

    //take the current item if the value doesn't exceed the limit
    if (current_sum + items[current_item] <= limit) {
        AddItem(items[current_item], knapsack);
        current_sum += items[current_item];
    };
    //current item taken go check others
    print_solutions(current_item + 1, knapsack, current_sum, items, n, limit);

};

int main() {
    int current_item = 0;
    int current_sum = 0;
    int limit, n;
    cout << "Type the maximum weight ";
    cin >> limit;
    cout << "How many items?  ";
    cin >> n;
    int* knapsack;
    knapsack = new int[10];
    for (int i = 0; i < 10; i++)
        knapsack[i] = -1;
    int * items;
    items = new int[n];

    cout << "Type weights.";
    for (int i = 0; i < n; i++) {
        cin >> items[i];
    };

    print_solutions(0, knapsack, 0, items, n, limit);

    return 0;

}

With the input:

7                       // limit
5                       // number of items 
1 1 3 4 5               // items

I expect to get the following final result:

[]
[5]
[4]
[3]
[3, 4]
[1]
[1, 5]
[1, 4]
[1, 3]
[1]
[1, 5]
[1, 4]
[1, 3]
[1, 1]
[1, 1, 5]
[1, 1, 4]
[1, 1, 3]

But all I get is arrays filled with 3 and 4 instead of getting all actual solutions.

Answer 1

In short

There is a major issue in your transcription of the algorithm from python to C++ related to the language semantics related to parameter passing.

In full details

When in python you write the following:

    print_solutions(current_item + 1, list(knapsack), current_sum)

Then list(knapsack) is a copy from the knapsack list. So the recursive call in the middle leaves the original knapsack unchanged, whereas the second recursive call changes the original knapsack:

print_solutions(current_item + 1, knapsack, current_sum)

In your C++ code however, in both case you work on the original knapsack list (the arrays parameters are passed by references), so that knapsack gets completely messed up:

//don't take the current item and go check others
print_solutions(current_item + 1, knapsack, current_sum, items, n, limit);

How to make it work ?

Either you create a temporary array and copy knapsack in it, or, much better, you start to use vector , which will make your C++ life much easier (making attention to pass by value or by reference).

The following version uses a vectors. The & in the parameter means that it's an argument passed by reference (i.e. the original vector can be changed). Note that we do no longer need to pass n, as the vector knows its length, as list do in python:

void print_solutions(int current_item, vector<int>& knapsack, int current_sum, const vector<int>& items, int limit) {  

    //if all items have been processed print the solution and return
    if (current_item == items.size() ) {
        printKnapsack(knapsack);
        return;
    };

    //don't take the current item and go check others
    vector<int> knapcopy = knapsack; 
    print_solutions(current_item + 1, knapcopy, current_sum, items, limit);

    //take the current item if the value doesn't exceed the limit
    if (current_sum + items[current_item] <= limit) {
        knapsack.push_back(items[current_item]);
        current_sum += items[current_item];
        //current item taken go check others
        print_solutions(current_item + 1, knapsack, current_sum, items, limit);
    };
};

Here an online demo.