Algorithms

Zero One Knapsack Dynamic Programming problem

5
(1)

Zero One Knapsack is one of the classic computer science problems which can be solved using dynamic programming concepts. Here let’s look at the problem statement and a recursive solution for the same.

Problem

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. In other words, given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item or don’t pick it (0-1 property).

package com.algo.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. In other words, given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and 
* weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out
* the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W. You 
* cannot break an item, either pick the complete item or don’t pick it (0-1 property).
* @author anupam
*
*/
public class ZeroOneKnapSack {

public static void main(String[] args) {
 int []val = {60, 100, 120};
 int []wt = {10, 20, 30};
 int w = 50;
 System.out.println(new ZeroOneKnapSack().profit(val, wt, w, 3));
}

/**
* Returns max profit that can be obtained
* @param val values of n items
* @param wt weights of n items 
* @param w total max weight that knapsack bag can contain
* @param n number of items in the array
* @return
*/
public int profit(int[]val, int[] wt, int w, int n) {
// Base case, if no items or no weight capacity then profit will be zero.
 if (n==0 || w==0) {
  return 0;
 }

 // Choice Dragon
 if (wt[n-1] > w) {
  return profit(val, wt, w, n-1);
 }
 else {
  int profitIfIncluded = val[n-1] + profit(val, wt, w-wt[n-1], n-1);
  int profitIfNotIncluded = profit(val, wt, w, n-1);
  return Math.max(profitIfIncluded, profitIfNotIncluded);
 }
}
}


How useful was this post?

Click on a star to rate it!

Average rating 5 / 5. Vote count: 1

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Tagged , ,
0 0 vote
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments