-5

リストのリストにレベルごとに格納されている知識のベースから達成できる最大の利益を計算して返す関数を作成する必要があります。

この機能をテストするためのメインは次のとおりです。

if __name__ == "__main__":
  l0 = [[7], [3,8], [8,1,0], [2,7,4,4], [4,5,2,6,5]]
  l1 = [[11], [7,32], [14,14,14], [0,1,2,3], [5,99,1,2,7],
       [0,25,9,45, 54,1], [99,88,77,66,55,44,33]]
>>>30
>>>270

私は下から上に始めようとしましたが、他の解決策はありますか?

リストはツリーのように想像できます

   [7]
  [3,8]
 [8,1,0]
[2,7,4,4]

などなど...最大のメリットがあるウォークに到達したい、選択肢の重みはリストの数字で与えられる、パスを最大化する必要がある

私はこの解決策を書きました

def maxpath(listN):
  liv = len(listN) -1
  return calcl(listN,liv)

def calcl(listN,liv):
  if liv == 0:
    return listN[0]
  listN[liv-1] = [(listN[liv-1][i]+listN[liv][i+1],listN[liv-1][i]+listN[liv][i]) \
                [ listN[liv][i] > listN[liv][i+1] ] for i in range(0,liv)]
  return calcl(listN,liv-1)

print(maxpath(l0))
print(maxpath(l1))

#output
[30]
[270]
4

1 に答える 1

1

ツリーを通る可能なルートの数は です2**rows。特定のノードへの可能なルートの数は、二項展開によって与えられます。ツリーの先頭から可能なルートを非常に簡単に成長させることができます.各ノードには次の移動が2つしかなく、リスト内のそれらのインデックスは現在の位置と同じか、それ以上です.

この問題を解決する簡単な方法は、指定された行数に対して可能なすべてのパスを生成することです。create_paths()これを行い、ツリーを介してすべての可能なルートを返します。関数max_cost()はこれを使用して、コスト ツリーに対してすべてのルートを評価し、最も高価なルートの値を返します。実際のルートを取得するのはあなたに任せます（それほど難しいことではありません..）:)

L_0 = [[7], [3,8], [8,1,0], [2,7,4,4], [4,5,2,6,5]]
L_1 = [[11], [7,32], [14,14,14], [0,1,2,3], [5,99,1,2,7],
       [0,25,9,45, 54,1], [99,88,77,66,55,44,33]]

def create_paths(rows):
    new_paths = []
    paths = [[0]]
    for row in xrange(rows):
        for path in paths:
            new_paths.append(path+[path[-1]])
            new_paths.append(path+[path[-1]+1])
        paths = new_paths
        new_paths = []
    return paths

def max_cost(tree):
    costs = []
    paths = create_paths(len(tree)-1)
    for path in paths:
        costs.append(sum([tree[i][j] for i, j in enumerate(path)]))
    return max(costs)

print max_cost(L_0)
print max_cost(L_1)

#output:
30
270
于 2012-05-15T08:22:06.680 に答える