0/1 Knapsack problem with solution

[6495 views]

Before diving into the main 0/1 knapsack problem, lets first know about the original knapsack problem. In a knapsack problem, you have a knapsack which has a limited space available. There are couple of items with different value and space. You need to select those items which fits in the knapsack and their value is maximum.
Say you have a knapsack which can handle 5KG weight, and you have 4Kg gold, 3kg silver and 7Kg bronze. Since we have to maximize the value, we have to take 4Kg of gold as its value is maximum. We are left with 1Kg space, here we can put 1Kg silver. Now our knapsack is full and we have the maximum value products.

0/1 Knapsack vs Fractional Knapsack

In both the problems, aim is the same, but there's a little difference. In fractional knapsack, we are allowed to select a fraction of the element, and in 0/1 knapsack, we can either select that element, or completely reject it. Fractional knapsack problem is rather easy and can be solved using greedy approach, whereas 0/1 knapsack problem is quite tricky and requires a dynamic approach.

0/1 knapsack problem

In this problem, we have a size of knapsack (W), n elements and each element e_i, has a value v_i and weight w_i. Lets say our knapsack has size W and these are the elements available to us.

A recursive approach can be, select/deselect first element, then for each selection, select/deselect second element. But this method has a exponential time complexity. So we go for dynamic approach.

Dynamic approach

To solve this problem through dynamic approach, we'll take a 2d array, whose first dimensions will represent each item, and second dimension will represent weight of knapsack.

For weight(0), or knapsack of size 0, we can have 0 items of weight 0, 0 items of weight 3, 0 items of weight 4 and 0 items of weight 5.

Now for knapsack of size 1, we can have 1 item of size 1, and since we have only one item of each type, for higher weights knapsack also, we can accomodate only 1 item of type 1.

Now for item 2 having weight 3, since weight 1, 2 knapsack cannot accomodate this item, for 1 and 2 size, we'll have 1 element only. for knapsack of size 3, we have an option of selecting item1 or item2, since value of item2 is greater, we select item2 whose value is 4.

For knapsack size 4, we can have both item1 as well as item2, hence total value will be 5. Filling the second row in similar fashion.

Now for item3 having weight 4, we have to copy the value till knapsack limit 3, on knapsack weight 4, we have an option of selecting/rejecting this item. If we select this item, we'll get a value 5, and if we reject this item, then also we have 5, from above row. Hence we write 5. Filling this row in the same fashion.

We get this matrix after filling the last row

So the maximum value that we can get is 9, but what about the elements ? We can get the selected elements by tracing back the array. While creating the array, we had an option to select the element or reject it on the basis of the value we were obtaining. Retracing our matrix, we get the following elements (marked with red).

So item2 and item3 were selected to have total value of 9.

Java Code:

import java.util.Scanner; public class Knapsack { private int n,W; //number of items and maximum capacity private int w[],v[]; //weights and values of items private int V[][]; //table to store results of sub-problems /** * Takes necessary inputs and initializes for solving */ private void initialize(){ Scanner sc = new Scanner(System.in); System.out.print("Enter number of items : "); n = sc.nextInt(); //number of items System.out.print("Enter W of knapsack : "); W = sc.nextInt(); //capacity of knapsack w = new int[n]; v = new int[n]; System.out.println("Enter ws and vs of items : "); for(int i = 0; i < n; i++){ w[i] = sc.nextInt(); //weight of item v[i] = sc.nextInt(); //profit of item } V = new int[n+1][W+1]; //initializing the table to hold results for(int i = 0; i <= W; i++) V[0][i] = 0; } /** * Computes the result */ public void knapsack(){ //table for backtracking to get the items chosen int x[][] = new int[n+1][W+1]; //filling tables for(int i = 1; i <= n; i++) for(int j = 0; j <= W; j++) if((w[i-1] <= j) && (v[i-1]+V[i-1][j-w[i-1]] > V[i-1][j])){ V[i][j] = v[i-1] + V[i-1][j-w[i-1]]; x[i][j] = 1; } else{ V[i][j] = V[i-1][j]; x[i][j] = 0; } //backtracking System.out.printf("Items Chosen\n%5s%7s%7s\n", "Item","Weight","Profit"); int K = W; for(int i = n; i >= 1; i--) if(x[i][K] == 1){ System.out.printf("%5d%7d%7d\n",i,w[i-1],v[i-1]); K -= w[i-1]; } System.out.println("Maximum profit : "+V[n][W]); } public static void main(String[] args) { Knapsack obj = new Knapsack(); obj.initialize(); obj.knapsack(); } }