1
私はPythonで新しく、多分それは愚かな質問かもしれません。再帰関数は作成された文字列を返しません
私は最終的にビットシーケンスを返す単純な再帰的なナップザックソリューションを実装しました。しかし、時にはそれは生成されるシーケンスを返さない。ここで私のコードとその結果をさまざまな入力にしています。
def knapsackRecursive(items, maxNum, bestResponse):
print('items=' + str(items) + ', maxNum=' + str(maxNum))
referenceIndex = 0
editableMaxNum = maxNum
if editableMaxNum == 0:
bestResponse = '0'
else:
for i in reversed(items):
item = int(i)
if editableMaxNum >= item:
if referenceIndex == 0:
referenceIndex = items.index(str(item))
editableMaxNum -= item
bestResponse = '1' + bestResponse
else:
bestResponse = '0' + bestResponse
if editableMaxNum != 0:
bestResponse = ''
if referenceIndex != 0:
for k in range(0, len(items) - referenceIndex):
bestResponse = '0' + bestResponse
knapsackRecursive(items[:referenceIndex], maxNum, bestResponse)
else:
bestResponse = '0'
print('bestResponse=' + str(bestResponse))
return bestResponse
Itemsは定数[ '1'、 '2'、 '4'、 '10'、 '20'、 '40'、 '63'、 '105']です。また、最初のbestResponseは空文字列です。
私は41としてmaxNumを設定した場合、出力は次のとおりです。
items=['1', '2', '4', '10', '20', '40', '63', '105'], maxNum=41
bestResponse=10000100
しかし、私は71としてmaxNumを設定した場合、出力は次のとおりです。
items=['1', '2', '4', '10', '20', '40', '63', '105'], maxNum=71
items=['1', '2', '4', '10', '20', '40'], maxNum=71
bestResponse=10011100
bestResponse=00
bestResponse出力は入力71のために二回印刷しないのはなぜ？そして、最初の印刷は正解ですが、関数が2番目の結果を間違って返すのはなぜですか？
EDIT
私はreturn knapsackRecursive(items[:referenceIndex], maxNum, bestResponse)としてknapsackRecursive(items[:referenceIndex], maxNum, bestResponse)を変更しました。それは解決されたようだ。明らかに、再帰的に使うと間違いがありました。しかし、私は、関数が正しい応答を生成することが期待される第2の呼び出しではなく、最初の呼び出しの結果を返すのはなぜなのか理解できませんでした。