title: Can I use dynamic programming to solve this?
body: <p>I have very little experience with dynamic programming.  I used it to solve a DNA alignment problem, a basic knapsack problem, and a simple pathfinding problem.  I understood how they worked, but it's not something I feel absolutely comfortable with yet.  </p>
  
  <p>I have a problem that reminds me of 0-1 dynamic programming, but the differences have thrown me off, and I'm not sure if I can still use this technique, or if I have to settle for a recursive approach.</p>
  
  <p>Let's say I have a list of items, each with different values, weights, and costs.  There may be more than one of each item.</p>
  
  <p>Let's say I have to choose a combo of those items which is the most valuable, but remains within the limits of weight and cost.  So far, I've described the knapsack problem, pretty much, with 2 constraints.  But here's the difference:</p>
  
  <p>The value of a chosen item changes depending on how many of them I have in the combo.  </p>
  
  <p>Let's say that each item has a function associated with it, that tells me what a group of those items is worth to me.  It's a basic linear function, such as 
  value_of_item = -3(quantity of that item) + 50</p>
  
  <p>So if I have 1 of some item in a combo, then it's value to me is 47.  If I had 2 of them, then they're only worth 44 to me, each.  </p>
  
  <p>If I use a dynamic programming table for this, then for each cell I'd have to backtrack to see if that item is already in the current combo, making DP pointless.  But maybe there's a way to re-frame the problem so I can take advantage of DP.</p>
  
  <p>Hopefully that made sense.  </p>
  
  <p>The alternative is to generate every combo of items, within the limits of cost and weight, figure the value of each combo, choose the most valuable combo.  For a list of 1000 items even, that's going to be an expensive search, and it's something I'd be calculating repeatedly.  I'd like to find a way to exploit the advantages of DP.</p>