私は動的プログラミングを理解するのが難しいので、いくつかの問題を解決することに決めました。私は、最も長い共通部分列、ナップザック問題のような基本的な動的アルゴリズムを知っていますが、読んだのでそれらを知っていますが、私自身は何かを考え出すことはできません:-(動的プログラミングに関する問題
たとえば、自然数の部分列があります。すべての番号は、我々はプラスまたはマイナスに取ることができます終わりに私たちは、この和の絶対値をとり、すべてのサブシーケンスは、可能な限り低い結果を見つけるために
IN1を：。。。10 3 5 4; OUT1：2
平方インチを：4 11 5 5 5; out2：0
in3：10 50 60 65 90 100; out3：5
説明3：5 = | 10 + 50 + 60 + 65-90-100 |
私の友人は、単純なナップサック問題だと言っていましたが、ナップザックは見えません。ダイナミックプログラミングは何かが難しいのですか、それとも大きな問題がありますか？
このアルゴリズムは、amitによって指摘されているように、partition problemのインスタンスとして理解できます。問題の入力のいずれかで呼び出されたとき
def partition(A):
n = len(A)
if n == 0:
return 0
k, s = max(A), sum(A)/2.0
table = [0 if x else 1 for x in xrange(n*k)]
for i in xrange(n):
for j in xrange(n*k-1, -1, -1):
if table[j-A[i]] > table[j]:
table[j] = 1
minVal, minIdx = float('+inf'), -1
for j in xrange(int(s)+1):
if table[j] and s-j < minVal:
minVal, minIdx = s-j, j
return int(2*minVal)
：シンプルな実装では、このPythonのコードを見てみましょう
partition([10, 50, 60, 65, 90, 100])
予想通りそれは、5を返します。ソリューションの背後にある数学を完全に理解するには、examplesを見て、「バランスのとれたパーティション」リンクをクリックしてください。
これは（関係ありません）バランスの取れたチームのサイズの制約なしに、綱引きのように同じ問題です：私はトップダウンアプローチでこの問題を解決していた http://acm.uva.es/p/v100/10032.html
。それは与えられた数に上限があるという制約で働く。上限がありますか、または数字に制約はありませんか？彼らが拘束されていない場合、私は動的プログラミングでこれを解決する方法を見ていません。
ここでのナップザックは、各要素についてweight = value = numberです。
あなたのバインドWは1/2 * sum(elements)です。
考え方は、1/2 * sum(elements)の制限を超えないで「選択」する数字の量を最大にしたいと考えています。ちょうどvalue=weightのナップザックです。
この問題は、実際にはpartition problemです。これはsubset sum problemの特別なケースです。
パーティションの問題は、「正確に半分になる要素のサブセットを取得できますか？
ここからあなたの問題への派生は簡単です - もしあれば+とし、取っていないものは-とし、out = 0としましょう。 [その逆の方法は同じ]。したがって、説明した問題はパーティションの問題の最適化です。
そのトップダウンアプローチは何ですか？ 数字が10000未満で、数字が5000未満です – xan
私はÓscarLópezによって投稿されたソリューションが私よりも優雅だと思います。 – ypnos