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
5 Years
Discussion Span
Last Post by Lucaci Andrew

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