Knapsack problem

You are given some denominations of coins in an array (int denom[])and infinite supply of all of them. Given an amount (int amount), find the minimum number of coins required to get the exact amount.


Java Code :

public class KnapSack {

 private static final int MIN = 232345;

 public static void main(String[] args) {
  int[] v = { 34, 12 };
  int amount = 2;

  int coins = getMinimumNumberOfCoins(v, amount);
  if (coins < MIN) {
   System.out.println("Coins required are : " + coins);
  } else {
   System.out
     .println("Cannot give denominations for the given amount");
  }

  int[] dp = new int[amount + 1];
  for (int i = 0; i <= amount; i++) {
   dp[i] = MIN;
  }

  coins = getMinimumNoOfCoinsDp_Recursion(v, amount, dp);
  if (coins < MIN) {
   System.out.println("DP : Coins required are : " + coins);
  } else {
   System.out
     .println("DP : Cannot give denominations for the given amount");
  }
 }

 private static int getMinimumNumberOfCoins(int[] v, int amount) {
  int minimum = MIN;
  if (amount == 0)
   minimum = 0;
  else if (amount > 0) {
   for (int i = 0; i < v.length; i++) {
    int temp = 1 + getMinimumNumberOfCoins(v, amount - v[i]);
    if (temp < minimum)
     minimum = temp;
   }
  }
  return minimum;
 }

 // Dp with recursion
 private static int getMinimumNoOfCoinsDp_Recursion(int[] v, int amount,
   int[] dp) {

  if (amount < 0)
   return MIN;

  if (dp[amount] < MIN)
   return dp[amount];

  int minimum = MIN;
  dp[0] = 0;
  if (amount == 0)
   minimum = 0;
  else if (amount > 0) {
   for (int i = 0; i < v.length; i++) {
    int temp = 1 + getMinimumNoOfCoinsDp_Recursion(v,
      amount - v[i], dp);
    if (temp < minimum)
     minimum = temp;
   }
  }
  return dp[amount] = minimum;
 }
}

Dynamic programming : 

public class KnapSack {

 private static final int MIN = 232345;

 public static void main(String[] args) {
  int[] v = { 34, 12 };
  int amount = 2;

  int coins = getMinimumNumberOfCoins_DP(v, amount);
  if (coins < MIN) {
   System.out.println("Coins required are : " + coins);
  } else {
   System.out
     .println("Cannot give denominations for the given amount");
  }
 }

 private static int getMinimumNumberOfCoins_DP(int[] v, int amount) {
  if (amount <= 0)
   System.out.println("Amount is zero");

  int[] min = new int[amount + 1];
  min[0] = 0;

  for (int i = 1; i <= amount; i++)
   min[i] = MIN;

  for (int i = 1; i <= amount; i++) {
   for (int j = 0; j < v.length; j++) {
    if (v[j] <= i && min[i - v[j]] + 1 < min[i])
     min[i] = min[i - v[j]] + 1;
   }
  }
  return min[amount];
 }
}

Refer : http://tech-queries.blogspot.com/2009/04/minimum-number-of-coins.html


0-1 knapsack problem