Knapsack Problem and Solution using Dynamic Programming

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible

• Given a knapsack of capacity m and number of items n of weight w1, w2, w3 ... , wn with profits p1, p2, p3..., pn.
• Let x1,x2,...,xn is an array that represents the items has been selected or not.

• If the item i is selected, then xi = 1
• If the item i is not selected then xi = 0

In 0/1 knapsack, the item can be selected or completely rejected. The items are not allowed to be broken into smaller parts.

The main objective is to place the items into the knapsack so that maximum profit is obtained or find the most valuable subset of items that fits into the knapsack.

Constraints: The weight of the items chosen should not exceed the capacity of knapsack.

Objective: Maximize the total of pi.xi where 1<= i <=n subject to contraint sum of  wi.xi <=m where xi =0 or 1.

0 | 1 knapsack problem exhibit optimal substructure property. To solve the problem using dynamic programming, we have to set up recurrence relation for it.


Design methodology using dynamic programming
let i represent the ith iem to be chosen to decide that it can be selected or not to maximize the profit with weight wi and profit pi with remaining capacity j. Then,

V[i, j] -- represents profit obtained by considering  ith item with remaining capacity j.

If we have the item i that fts into the knapsack with capacity j, is divided into two categories -

1. that do not include ith item
2. that include ith item

various cases to be considered are :

Base Case: 

• If there are no items (i.e i ==0) then V[0, j] = 0
• if there is 0 capacity of knapsack(i.e no bag/knapsack) the V[i, 0] = 0
• Total profit obtained v[i, j] = 0 if i = 0 or j = 0.

general Case:

• For ith item, wi > j (remaining capacity) then ith item cannot be selected. so total profit obtained V[i, j] = V[i-1, j] if wi > j.
• For ith item, wi <=j (remaining capacity) then if ith item is selected, the total profit obtained V[i, j] = V[i-1, j-w[i]] + pi
• If ith item is rejected, the total profit obtained V[i, j] = V[i-1, j] so, the total profit obtained if wi<=j,   V[i, j] = max {V[i-1, j] , V[i-1 , j-w[i]+Pi}; if wi<=j
• 
  

The recurrence relation is given by
V[i,j] = max{V[i-1, j], V[i-1, j-wi] +pi} if j-wi>=0
V[i-1, j] if j-wi <0 br="">0 if i=0 or j=0

V[n,m]  gives the value of the optimal solution.

Set of items to be taken in knapsack can be found from the table as below  -

• Start at V[n,m] ad track backward where the optimal solution came from.
• If V[i, j] = V[i-1, j], thenitem i is not part of the solution and we continue tracing from V[i-1, j].
• otherwisem item i is part of the solution and we continue tracing with V[i-1, j-wi]

Below is the java program for the above given algorithm

public class KnapsackSolution {

public int knapsack(int profit[], int weight[], int noOfItems, int capacity){

int[][] solutionMatrix = new int[noOfItems+1][capacity+1];

for(int i=0; i<=noOfItems; i++ ){

for(int j=0; j<=capacity; j++){

if(i==0||j==0){

solutionMatrix[i][j] = 0;

}else if(weight[i-1] > j){

solutionMatrix[i][j] = solutionMatrix[i-1][j] ;

}else{

solutionMatrix[i][j] = Math.max(solutionMatrix[i-1][j], profit[i-1]+solutionMatrix[i-1][j-weight[i-1]]);

}

}

}

System.out.println("====Solution Matrix=====");

for(int[] row : solutionMatrix){

for(int cell : row){

System.out.print(cell+"\t");

}

System.out.println();

}

System.out.println("=========================");

System.out.println("Maximum profit:"+solutionMatrix[noOfItems][capacity]);

//optimal solution vector

int[] optimalSolution = new int[noOfItems];

int i = noOfItems;

int j = capacity;

while(i != 0 && j!=0){

if(solutionMatrix[i][j] != solutionMatrix[i-1][j]){

optimalSolution[i-1] = 1;

j= j-weight[i-1];

}

i=i-1;

};

System.out.println("====solution vector=====");

for(int sol : optimalSolution)

System.out.print(sol+"\t");

System.out.println();

return solutionMatrix[noOfItems][capacity];

}

public static void main(String args[]){

int p[] = new int[]{12,10,20,15};

int w[] = new int[]{2,1,3,2};

int noOfItems = 4;

int capacity = 5;

KnapsackSolution k = new KnapsackSolution();

k.knapsack(p, w, noOfItems, capacity);

}

}