1

After exploring this question I came to realize that dynamic programming algorithms can't be used to solve knapsack problem or similar problems with a non-integer constraint. Am I right about my realization? Are there any other limitations of Dynamic Programming algorithms?

Community
  • 1
  • 1
Sajib Mahmood
  • 3,382
  • 3
  • 37
  • 50
  • 3
    I imagine that in addition to here, the folks at the Theoretical Computer Science stack exchange (http://cstheory.stackexchange.com/) would have a lot of insight into this question. – John with waffle Jan 21 '12 at 13:32

2 Answers2

2

Basically you could say the number of possible scores (solution quality) needs to be finite and low enough to fit in memory. Non-integer in general means non-discrete and that leads to infinite possible solution scores.

If there are only N possible solution scores you know that you will at most need to find N of them to also get the best one, not the whole exponential amount of ways to get to them. That's the idea behind dynamic programming.

ypnos
  • 50,202
  • 14
  • 95
  • 141
1

I suppose another limitation is that it isn't known if dynamic programming is the best available technique, given that its performance isn't known to match information theoretic lower bounds.

Here is an example problem from David Eppstein:

Given a sorted list of n real numbers, find the smallest interval containing exactly k elements, for all values of k between 1 and n. There is a simple dynamic programming algorithm that solves this problem in quadratic time, but the best known lower bound is only linear. Either describe a faster algorithm, or prove a bigger lower bound in some reasonable model of computation. ("Dynamic programming" is not a reasonable model of comptuation!!)

John with waffle
  • 4,113
  • 21
  • 32