動的プログラミングアルゴリズムの制限

Question

この後、questionを探索したところ、knapsack problemまたは非整数制約を使用して動的プログラミングアルゴリズムを使用して解決することはできません。私の実現について正しいのですか？ダイナミックプログラミングアルゴリズムには他にも限界がありますか？

Answer 1

基本的に、可能なスコアの数（解の品質）は有限であり、メモリに収まるのに十分に低いと言えるでしょう。非整数とは一般に非離散を意味し、無限の可能な解の得点につながります。

N個の解決策スコアしかない場合は、N個の解決スコアを取得する必要があります。指数関数的なものではありません。それは動的プログラミングの背後にあるアイデアです。

Answer 2

私は、ダイナミックプログラミングが情報理論上の下限と一致することが知られていないので、ダイナミックプログラミングが最高の利用可能な技術であるかどうかはわかりません。ここ

はan example problem from David Eppsteinである：nは実数のソートされたリストが与えられる

、1とnの間のkのすべての値について正確にk個の要素を含む最小間隔 を見つけます。 二次的な時間にこの の問題を解決する簡単な動的プログラミングアルゴリズムがありますが、最もよく知られている下限は linearです。より速いアルゴリズムを記述するか、計算のいくつかの妥当なモデルでより大きなより低い値を に結びつけてください。