Write an algorithm for Knapsack Problem?

Answer 1

Answer

The pseudocode listed below is for the unbounded knapsack problem.

operation ub-ks (n, K)
// n is the total number of items, K is the capacity of the knapsack
{
for (int h = 0; h < K; h++)
V[0, h] = 0; // initializes the bottom row of the table
for (int i = 0; i < n; i++) {
for (int kp = 0; kp < K; kp++) {
ans = V[i-1, kp]; // case 1: item i not included
if (size[i] <= kp) { // if the ith item's size is less than kp...
other = val[i] + V[i-1, kp - size[i]];
// ...then case 2: item i is included
if (other > ans) // case 3: both are possible, so take the max
ans = other;
V[i, kp] = ans;
}
}
}
return V[n, K];
} // end ub-ks

Answer 2

Merkle-Hellman's Knapsack algorithm is based on the NP-class "knapsack" problem, in which a series of items with different weights are put into a knapsack capable of holding a certain weight S. As an example, take the objects of weight 1, 4, 6, 11, 17, and 29 where the S can be equal to 11 (1+4+6, or just 11) and not 13. The time necessary to solve this problem increases exponentially as the number of items increase, as the only conventional method being exhaustive search, and is easily solvable with 5 objects but not 1000.