0

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.

Edited by subith86

3
Contributors
2
Replies
3
Views
4 Years
Discussion Span
Last Post by Lucaci Andrew
0

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

0

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.

Edited by Lucaci Andrew

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.