title: Knapsack: how to add item type to existing solution
body: <p>I've been working with this variation of dynamic programming to solve a knapsack problem:</p>
  
  <pre><code>KnapsackItem = Struct.new(:name, :cost, :value)
  KnapsackProblem = Struct.new(:items, :max_cost)
  
  
  def dynamic_programming_knapsack(problem)
    num_items = problem.items.size
    items = problem.items
    max_cost = problem.max_cost
  
    cost_matrix = zeros(num_items, max_cost+1)
  
    num_items.times do |i|
      (max_cost + 1).times do |j|
        if(items[i].cost &gt; j)
          cost_matrix[i][j] = cost_matrix[i-1][j]
        else
          cost_matrix[i][j] = [cost_matrix[i-1][j], items[i].value + cost_matrix[i-1][j-items[i].cost]].max
        end
      end
    end
  
    cost_matrix
  end
  
  def get_used_items(problem, cost_matrix)
    i = cost_matrix.size - 1
    currentCost = cost_matrix[0].size - 1
    marked = Array.new(cost_matrix.size, 0) 
  
    while(i &gt;= 0 &amp;&amp; currentCost &gt;= 0)
      if(i == 0 &amp;&amp; cost_matrix[i][currentCost] &gt; 0 ) || (cost_matrix[i][currentCost] != cost_matrix[i-1][currentCost])
        marked[i] = 1
        currentCost -= problem.items[i].cost
      end
      i -= 1
    end
    marked
  end
  </code></pre>
  
  <p>This has worked great for the structure above where you simply provide a name, cost and value. Items can be created like the following:</p>
  
  <pre><code> items = [
        KnapsackItem.new('david lee', 8000, 30) , 
        KnapsackItem.new('kevin love', 12000, 50), 
        KnapsackItem.new('kemba walker', 7300, 10),
        KnapsackItem.new('jrue holiday', 12300, 30),
        KnapsackItem.new('stephen curry', 10300, 80),
        KnapsackItem.new('lebron james', 5300, 90),
        KnapsackItem.new('kevin durant', 2300, 30),
        KnapsackItem.new('russell westbrook', 9300, 30),
        KnapsackItem.new('kevin martin', 8300, 15),
        KnapsackItem.new('steve nash', 4300, 15),
        KnapsackItem.new('kyle lowry', 6300, 20),
        KnapsackItem.new('monta ellis', 8300, 30),
        KnapsackItem.new('dirk nowitzki', 7300, 25),
        KnapsackItem.new('david lee', 9500, 35),
        KnapsackItem.new('klay thompson', 6800, 28)
      ]
  
    problem = KnapsackProblem.new(items, 65000)
  </code></pre>
  
  <p>Now, the problem I'm having is that I need to add a position for each of these players and I have to let the knapsack algorithm know that it still needs to maximize value across all players, except there is a new restriction and that restriction is each player has a position and each position can only be selected a certain amount of times. Some positions can be selected twice, others once. Items would ideally become this:</p>
  
  <pre><code>KnapsackItem = Struct.new(:name, :cost, :position, :value)
  </code></pre>
  
  <p>Positions would have a restriction such as the following:</p>
  
  <pre><code>PositionLimits = Struct.new(:position, :max)
  </code></pre>
  
  <p>Limits would be instantiated perhaps like the following:</p>
  
  <pre><code>limits = [Struct.new('PG', 2), Struct.new('C', 1), Struct.new('SF', 2), Struct.new('PF', 2), Struct.new('Util', 2)]
  </code></pre>
  
  <p>What makes this a little more tricky is every player can be in the Util position. If we want to disable the Util position, we will just set the 2 to 0. </p>
  
  <p>Our original items array would look something like the following:</p>
  
  <pre><code>items = [
            KnapsackItem.new('david lee', 'PF', 8000, 30) , 
            KnapsackItem.new('kevin love', 'C', 12000, 50), 
            KnapsackItem.new('kemba walker', 'PG', 7300, 10),
            ... etc ...
          ]
  </code></pre>
  
  <p>How can position restrictions be added to the knapsack algorithm in order to still retain max value for the provided player pool provided?</p>