Solving Knapsack using Dynamic Programming (C/Java Implementation)

knapsack using Dynamic Programming

We’ll be solving Knapsack using Dynamic programming in Java and C. The knapsack problem is a commonly asked question in Technical interviews. Interviewers use this question to test the ability of a candidate in Dynamic Programming.

It is also one of the most basic questions that a programmer must go over when learning Dynamic Programming.

Dynamic Programming is an algorithmic technique for solving an optimization problem by breaking it down into simpler subproblems and utilizing the fact that the optimal solution to the overall problem depends upon the optimal solution to its subproblems.

Problem statement for 0/1 Knapsack

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack.

We are going to look at the 0/1 knapsack problem in this tutorial. In 0/1 knapsack, an item can either be included as a whole or excluded.

The main goal of the problem is to maximize the profit (sum of values) while staying within the weight limit.

Weights and values of items are taken in two arrays of size n each.

For example:

Let the value array be:

{ 60, 100, 120 }

The weight array be:

{ 10, 20, 10 }

The weight limit is 30.

Then to get the maximum value we will pick the objects 2 and 3.

That will give us a total of:

100 + 120 = 220 

Solving The Knapsack Problem

To solve the knapsack problem using Dynamic programming we build a table. The table has the following dimensions:

[n + 1][W + 1]

Here each item gets a row and the last row corresponds to item n. We have columns going from 0 to W. The index for the last column is W.

The very last cell of this matrix has the index:

[n][W]

After filling the table, this cell will contain the answer.

Filling of the table

While filling a cell in the table our goal is to stay within the weight limit that is equal to the column number and use items from 1 to that row number.

If we are filling the cell [i] [j] then we can use items from 1 to i and the weight limit is j.

For row i, we have the option of including item i in our collection. The previous row that it row i-1 contains the maximum weight possible without including the ith item. If by including the ith item we are able to achieve a higher value then we include the ith item in our answer.

In terms of code, we do this as follows :

 for (i = 0; i<= n; i++) { 
            for (w = 0; w<= W; w++) { 
                if (i == 0 || w == 0) 
                    K[i][w] = 0; 
                else if (wt[i - 1]<= w) 
                    K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]); 
                else
                    K[i][w] = K[i - 1][w]; 
            } 
        } 
  
        return K[n][W]; 
    } 

This piece of code shows how the table is filled in a bottom up manner.

The algorithm for the same is as follows:

  1. Set the value of 0th row and column to 0.
  2. Iterate over the matrix with i -> [1,n] & w -> [1,W]
  3. To fill cell [i, j] :
    1. If the weight of ith item < w then cell value is maximum of (val[i – 1] + K[i – 1][w – wt[i – 1]], K[i – 1][w])
    2. Else cell value is K[i – 1][w]
  4. Return K[n][W]

Here the term K[i – 1][w] means that ith item is not included. The term val[i – 1] + K[i – 1][w – wt[i – 1]] represents that the ith item is included.

Note : val [i-1] gives the value of ith item since the start index for the array val is zero.

Solving the Knapsack Problem in Java and C

Complete Java code :

package com.JournalDev;

import static java.lang.Integer.max;

class Kanpsack
{
    static int knapSack(int W, int wt[], int val[], int n)
{
    int i, w;
    int K[][] = new int[n + 1][W + 1];

    
    for (i = 0; i<= n; i++) {
        for (w = 0; w<= W; w++) {
            if (i == 0 || w == 0)
                K[i][w] = 0;
            else if (wt[i - 1]<= w)
                K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
            else
                K[i][w] = K[i - 1][w];
        }
    }

    return K[n][W];
}

   
    public static void main(String args[])
    {
        int val[] = new int[] { 60, 100, 120 };
        int wt[] = new int[] { 10, 20, 10 };;
        int W = 30;
        int n = val.length;
        System.out.println(knapSack(W, wt, val, n));
    }
}

        

Code in C :

#include <stdio.h> 
  
// function to get maximum of two integers 
int max(int a, int b) 
{ 
    return (a > b) ? a : b; 
} 
 
int knapSack(int W, int wt[], int val[], int n) 
{ 
    int i, w; 
    int K[n + 1][W + 1]; 
  
    for (i = 0; i <= n; i++) { 
        for (w = 0; w <= W; w++) { 
            if (i == 0 || w == 0) 
                K[i][w] = 0; 
            else if (wt[i - 1] <= w) 
                K[i][w] = max( 
                    val[i - 1] + K[i - 1][w - wt[i - 1]], 
                    K[i - 1][w]); 
            else
                K[i][w] = K[i - 1][w]; 
        } 
    } 
  
    return K[n][W]; 
} 
  
int main() 
{ 
    int val[] = { 60, 100, 120 }; 
    int wt[] = { 10, 20, 10 }; 
    int W = 30; 
    int n = sizeof(val) / sizeof(val[0]); 
    printf("%d", knapSack(W, wt, val, n)); 
    return 0; 
} 

Output

220 

Conclusion

This tutorial was about solving 0/1 Knapsack using Dynamic programming. If you want to learn more about Dynamic Programming then read our tutorial on solving the Subset sum problem using Dynamic Programming.

Leave a Reply

Your email address will not be published. Required fields are marked *

close
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages