/**
 * This file contains a dynamic programming solutions to the classic unbounded
 * knapsack problem where are you are trying to maximize the total profit of
 * items selected without exceeding the capacity of your knapsack.
 * 
 * Version 1:
 * Time Complexity: O(nW)
 * Version 1 Space Complexity: O(nW)
 *
 * Version 2:
 * Time Complexity: O(nW)
 * Space Complexity: O(W)
 * 
 * Tested code against:
 * https://www.hackerrank.com/challenges/unbounded-knapsack
 * 
 * @author William Fiset, william.alexandre.fiset@gmail.com
 **/
package com.williamfiset.algorithms.dp;

public class KnapsackUnbounded {
  
  /**
   * @param maxWeight - The maximum weight of the knapsack
   * @param W - The weights of the items
   * @param V - The values of the items
   * @return The maximum achievable profit of selecting a subset of
   * the elements such that the capacity of the knapsack is not exceeded
   **/
  public static int unboundedKnapsack(int maxWeight, int[] W, int[] V) {
    
    if (W == null || V == null || W.length != V.length || maxWeight < 0) 
      throw new IllegalArgumentException("Invalid input");
    
    final int N = W.length;
    
    // Initialize a table where individual rows represent items 
    // and columns represent the weight of the knapsack
    int[][] DP = new int[N+1][maxWeight+1];
    
    // Loop through items
    for (int i = 1; i <= N; i++) {
      
      // Get the value and weight of the item
      int w = W[i-1], v = V[i-1];
      
      // Consider all possible knapsack sizes
      for (int sz = 1; sz <= maxWeight; sz++) {
        
        // Try including the current element
        if (sz >= w) DP[i][sz] = DP[i][sz-w] + v;
        
        // Check if not selecting this item at all is more profitable
        if (DP[i-1][sz] > DP[i][sz]) DP[i][sz] = DP[i-1][sz];
        
      }
      
    }

    // Return the best value achievable
    return DP[N][maxWeight];
    
  }
  
  public static int unboundedKnapsackSpaceEfficient(int maxWeight, int[] W, int[] V) {
    
    if (W == null || V == null || W.length != V.length) 
      throw new IllegalArgumentException("Invalid input");
    
    final int N = W.length;
    
    // Initialize a table where we will only keep track of 
    // the best possible value for each knapsack weight
    int[] DP = new int[maxWeight+1];
    
    // Consider all possible knapsack sizes
    for (int sz = 1; sz <= maxWeight; sz++) {
      
      // Loop through items
      for (int i = 0; i < N; i++) {
        
        // First check that we can include this item (we can't include it if 
        // it's too heavy for our knapsack). Assumming it fits inside the 
        // knapsack check if including this element would be profitable.
        if (sz - W[i] >= 0 && DP[sz-W[i]] + V[i] > DP[sz])
          DP[sz] = DP[sz-W[i]] + V[i];
        
      }
      
    }
    
    // Return the best value achievable
    return DP[maxWeight];
    
  }  

  public static void main(String[] args) {
    
    int[] W = {3,  6, 2};
    int[] V = {5, 20, 3};
    unboundedKnapsackSpaceEfficient(10, W, V);
    
  }

}











@@ -2922,21 +2922,16 @@
 eight%5D;%0A
-    %0A
   %7D  %0A%0A 
@@ -3032,16 +3032,36 @@
  3%7D;%0A   
+ int knapsackValue =
  unbound
@@ -3104,22 +3104,83 @@
     
-%0A  %7D%0A%0A%7D%0A%0A%0A%0A%0A%0A%0A%0A%0A
+System.out.println(%22Maximum knapsack value: %22 + knapsackValue);%0A    %0A  %7D%0A  %0A%7D
 %0A%0A

Update KnapsackUnbounded.java