Knapsack problem extension - Identifying the weights being used.

[subith86]

I have a code which gives the maximum value I can get by filling the knapsack with the optimal set of weights.

int arr[5] = {0, 0, 0, 0, 0};
int Weight[5] = {2, 5, 8, 7, 9};
int Value[5]  = {4, 5, 7, 9, 8};
const int n = 5;
const int maxCapacity = 20;

int maximum(int a, int b)
{
    return a > b ? a : b;
}

int knapsack(int capacity, int i)
{
    if (i > n-1) return 0;

    if (capacity < Weight[i])
    {
        return knapsack(capacity, i+1);
    }
    else
    {
        return maximum (knapsack(capacity, i+1),
                        knapsack(capacity - Weight[i], i+1) + Value[i]);
    }
}

int main (void)
{
    cout<<knapsack(maxCapacity,0)<<endl;
    return 0;
}

I need to extend this solution by printing which all weights are used to find the optimal solution. For this I plan to use an array arr initialized to 0. Whenever a weight is used I mark the corresponding position in arr by 1, otherwise it remains 0.

First thing that came into my mind is to change the maximum() function like shown below

int maximum(int a, int b, int i)
{
    if (a > b)
    {
        if (arr[i] == 1) arr[i] = 0;
        return a;
    }
    else
    {
        if (arr[i] == 0) arr[i] = 1;
        return b;
    }
}

But even this solution fails for some combination of weights and values. For illustration purpose, I have hard coded the values which fail. Any suggestions on how to go forward?

PS: This question is posted by me in another forum too for which I didn't get answer. Please don't mind if you come across a duplicate.

[iamthwee]

Knapsack problem? OK we can probably google this but it's best to provide a link just so the people helping you are clear?

[Lucaci Andrew]

Here's the link from wiki Click Here
Here's a good totorial on the knapsack problem using dynamic programming Click Here maybe this approach would suite you better than the "hard coding" one.