Description: Given a knapsack with maximum capacity W, and a set S consisting of n items Each item i has some weight wi and benefit value bi  (all wi  and W are integer values)  Problem: How to pack the knapsack to achieve maximum total value of packed items?

Solution:

Recursive formula :

where V[k,w] denotes an optimal solution for Sk = {items labeled 1, 2, .. k} in a knapsack of size w
The above formula means that the best subset of Sk that has total weight w is:
1) the best subset of Sk-1 that has total weight £ w,    or
2) the best subset of Sk-1 that has total weight £ w- wk plus the item k

Algorithm:

for w = 0 to W
V[0,w] = 0
for i = 1 to n
V[i,0] = 0
for i = 1 to n
for w = 1 to W
if wi <= w /* item i can be part of the solution */
if bi + V[i-1,w-wi] > V[i-1,w]
V[i,w] = bi + V[i-1,w- wi]
else
V[i,w] = V[i-1,w]
else V[i,w] = V[i-1,w]  // wi > w

C Implementation:

/* A Dynamic Programming based solution for 0-1 Knapsack problem */

#include<stdio.h>

/* A utility function to calculate maximum of two integers */
int max(inta, intb) { return(a > b)? a : b; }

/* Returns the maximum value that can be put in a knapsack of capacity W */
int knapSack(int W, int wt[], int val[], int n)
{
inti, w;
intV[n+1][W+1];

/* Build table V[][] in bottom up manner */
for(i = 0; i <= n; i++)
{
for(w = 0; w <= W; w++)
{
if(i==0 || w==0)
V[i][w] = 0;
elseif(wt[i-1] <= w)
V[i][w] = max(val[i-1] + V[i-1][w-wt[i-1]],  V[i-1][w]);
else
V[i][w] = V[i-1][w];
}
}

returnV[n][W];
}

Time complexity:

O(nW) where n is the number of items and W is the capacity of knapsack.

Go to top