2

現在、アルゴリズムのクラスを受講しています。動的プログラミングを含め、Pythonでそれらの多くをテストしています。これは、ボトムアップのロッド切断の実装です。

off-by-one エラーのため動作しません。デフォルトの配列インデックスを 0 ではなく 1 に変更できる Python のグローバル設定はありますか? または、誰かが、私が何百万回も遭遇するオフバイワンエラーを克服するためのより良い戦略を教えてください. 超迷惑です。

def bottom_up_memo_cut_rod(p,n):
    r = [ 0 for i in range(n) ]
    r[0] = 0
    for j in range(n):
        q = -1
        for i in range(j):
            q = max(q, p[i] + r[j-i])
        r[j] = q
    return r[n]

bottom_up_memo_cut_rod([1,5,8,9], 4)

この場合、答えは 10 である必要があり、4 を (2,2) に分割すると、最大価格は 10 になります。

4

3 に答える 3

3

Python には、役立つ可能性のあるものがいくつかあります。組み込みenumerateは素晴らしいものです。

for idx, val_at_idx in enumerate(aList):
  # idx is the 0-indexed position, val_at_idx is the actual value.

絶対に必要な場合は、enumerate でリスト スライスを使用してインデックスをシフトすることもできます。

for idxOffBy1, val_at_wrong_idx in enumerate(aList[1:]):
  # idx here will be 0, but the value will be be from position 1 in the original list.

ただし、現実的には、リストがインデックス 1 から始まるようにインタープリターを変更したくはありません。言語で動作するようにアルゴリズムを調整する必要があります。

于 2012-10-26T18:20:30.583 に答える
2

Python では、多くの場合、インデックスの操作を完全に回避できます。そのアルゴリズムは次のように記述できます。

def bottom_up_memo_cut_rod(p,n):
    r = [0]
    for dummy in p:
        r.append(max(a + b for a, b in zip(reversed(r),p)))
    return r[-1]

print bottom_up_memo_cut_rod([1,5,8,9], 4)
#10
于 2012-10-26T19:11:19.527 に答える
-1

あなたの場合、off-by-one はr[n]whereの結果ですlen(r)==n。r[n-1]、または、より好ましくはr[-1]、「の最後の要素」を意味する、と書くかr、同じ方法でr[-2]「最後から2番目」などを意味します。

無関係ですが、便利です: 次の[ 0 for i in range(n) ]ように記述できます。[0] * n

于 2012-10-26T18:20:35.120 に答える