0

問題は、ツインパン天びんで与えられた重みのセットで目的の値のターゲットを測定できるかどうかを判断する再帰関数「defEhMensuravel（target、weight）」を作成することです。使用可能な重みは、リスト「重み」に格納されます。おもりは、ターゲットウェイトが占めるプレートの反対側、ターゲットウェイトの同じプレート、または使用しないプレートに配置できることを思い出してください。

私が作成したコードはそれですが、何かが間違っています。

weights = [1, 2, 3]
matrix = []

def createaMatrix():
    for i in range(len(weights)):
        matrix.append([])
    for j in range(3):
        for i in range(len(weights)):
            if j==0:
                matrix[j].append(weights[i])
            if j==1:
                matrix[j].append(-weights[i])
            if j==2:
                matrix[j].append(0)

createMatrix()


def EhMensuravel(entry, weights, final_weight=0):
    if final_weight == entry:
        return True
    for j in range(3):
        for i in range(len(weight)):
            final_weight += matrix[i][j]
            return EhMensuravel(entry, weight[1:], final_weight)

編集：たとえば、試してみるprint EhMensuravel(4, weights)と、出力は次のようになります。

>>> 
1
2
3
None
>>>
4

1 に答える 1

1

このようなグローバルマトリックスがなくても、再帰を非常に単純にすることができます

weights = [1, 2, 3]

def EhMensuravel(entry, weights, weight_idx = 0):
    if entry == 0:
        return True

    if weight_idx == len(weights):
        return False

    if EhMensuravel(entry + weights[weight_idx], weights, weight_idx+1):
        return True

    if EhMensuravel(entry - weights[weight_idx], weights, weight_idx+1):
        return True

    if EhMensuravel(entry, weights, weight_idx+1):
        return True

    return False

print EhMensuravel(4, weights)

最初の if ステートメントは、0 が測定可能であることを示しています。2 番目の if は、重みがまだ残っていることを保証します。次の 3 つの再帰呼び出しは、現在の重みentryを加算、減算、または無視することによって現在の重みを更新し、次の重みから検索を再開します。解が見つからない場合は、False が返されます。

于 2013-02-18T23:34:46.623 に答える