CODEWITHSUNDEEP
dynamic-programmingknapsack-problem
user2441151
user2441151

Reputation: 1562

Why is this algorithm for the integer knapsack incorrect?

This is what I think I need to do.

Given 'n' items of weight 'Wi' and value 'Vi', I need to maximize the value of the knapsack while staying under the weight limit WEIGHT_MAX.

So, what I thought of doing was, sorting the items according to their value ( High to low ), and then choosing items as long as the weight of the knapsack is less than WEIGHT_MAX.

i.e. something like this

while( temp_weight <= WEIGHT_MAX && i <= INDEX_MAX )
{
   if ( temp_weight + W[i] > WEIGHT_MAX ) { i++; continue;}
   temp_weight += W[i];
   value += V[i];
   i++;
}

Why is this algorithm wrong?

Upvotes: 1

Views: 193

Answers (1)

jbgs
jbgs

Reputation: 2885

Consider these sorted elements:

Vi={10, 5, 5, 5, 5, 5, 5}

Wi={4, 1, 1, 1, 1, 1, 1}

With your algorithm if your WEIGHT_MAX is 4, you would choose just the V=10 element (total value 10). But the optimal solution would be 4 elements with V=5 (total value 20).

That's why your algorithm doesn't lead to optimum.

A few algorithms to solve it: http://en.wikipedia.org/wiki/Knapsack_problem

Upvotes: 1

Related Questions