title: Modified Knapsack algorithm
body: <p>I've different classes of items. Each item has <code>value</code> and <code>weight</code>. </p>
  
  <p>For example:</p>
  
  <p><code>ClassA: [A1, A2, A3]</code></p>
  
  <p><code>ClassB: [B1, B2, B3]</code></p>
  
  <p><code>ClassC: [C1, C2, C3]</code></p>
  
  <p>How should I modify classic 0-1 Knapsack problem so that algorithm optimize solution maximizing overall value, consider all items in class but allowed to pick at at most one item from one class?</p>
  
  <pre><code>package knapsack;
  
  import java.util.ArrayList;
  import java.util.List;
  
  public class Knapsack {
  
      private int totalNumberOfItems;
      private int maxmimumKnapsackCapacityUnits;
  
      private double[][] optimum;
      private boolean[][] solution;
  
      private double [] value;
      private int [] weight;
  
      public Knapsack(int knapsackCapacityUnits, List&lt;KnapsackItem&gt; items){
  
          this.totalNumberOfItems = items.size();
          this.maxmimumKnapsackCapacityUnits = knapsackCapacityUnits;
  
          this.optimum = new double[items.size() + 1][knapsackCapacityUnits + 1];
          this.solution = new boolean[items.size() + 1][knapsackCapacityUnits + 1];
  
          this.value = new double[items.size() + 1];
          this.weight = new int[items.size() + 1];
  
          int index=1;
          for(KnapsackItem item : items){
              value[index] = item.value;
              weight[index] = item.weight;
              index++;
          }
  
  
  }
  
  public List&lt;KnapsackItem&gt; optimize(){
  
      for(int currentItem = 1; currentItem &lt;= totalNumberOfItems; currentItem++){
          for(int currentWeightUnit = 1; currentWeightUnit &lt;= maxmimumKnapsackCapacityUnits; currentWeightUnit++){
  
              double option1 = optimum[currentItem - 1][currentWeightUnit];
  
              double option2 = Integer.MIN_VALUE;
  
              if(weight[currentItem] &lt;= currentWeightUnit){
                  option2 = value[currentItem] + optimum[currentItem-1][currentWeightUnit - weight[currentItem]];
              }
  
              optimum[currentItem][currentWeightUnit] = Math.max(option1, option2);
              solution[currentItem][currentWeightUnit] = (option2 &gt; option1);
          }
      }
  
      boolean take [] = new boolean[totalNumberOfItems + 1];
      for(int currentItem = totalNumberOfItems,
              currentWeightUnit = maxmimumKnapsackCapacityUnits; 
              currentItem &gt; 0; currentItem --){
          if(solution[currentItem][currentWeightUnit]){
              take[currentItem] = true;
              currentWeightUnit = currentWeightUnit - weight[currentItem];
          }
          else{
              take[currentItem] = false;
          }
      }
  
      List&lt;KnapsackItem&gt; items = new ArrayList&lt;KnapsackItem&gt;();
      for(int i = 0; i &lt; take.length; i++){
          KnapsackItem newItem = new KnapsackItem();
          newItem.value = value[i];
          newItem.weight = weight[i];
          newItem.isTaken = take[i];
          items.add(newItem);
      }
  
      return items;
  }
  }
  </code></pre>
  
  <p>Thanks!</p>