pythonは再帰に基づいてリュックサックの問題を解決します。
再帰的には良いもので、再帰的な性質を持つ問題は関数再帰的に呼び出されると簡単になります。複雑な問題です。何行かのコードで解決できます。
最も簡単な再帰問題:既存の重さはweightのカバンで、いくつかの重さはそれぞれW 1、W 2…。Wnのものは、品物の中からいくつかのものを選ぶことができますか?しかも重さはちょうどweightですか?
weightは具体的にどのように構成されていますか?次の二つの場合があります。
1. Wn-1からweightになります。weight=W 1+W 2+…+Wn=W 1+W 2+…+Wn 1.
2.Wnを加えるとちょうどweightになります。自然にweight=W 1+W 2+…+Wnがあります。
上の二つの状況は一つでも解があるので、Wiをバックパックから消して戻ってweightの値を見ることができます。
一連の逆押しを経て、weightの値は次の3つの場合があります。
1.weightはちょうど0//説明が解ります。
2. weight<0/ありえないので、分かりません。
3.weight>0 and Wがありません ありえない
以上が本文の全部です。皆さんの勉強に役に立つように、私たちを応援してください。
最も簡単な再帰問題:既存の重さはweightのカバンで、いくつかの重さはそれぞれW 1、W 2…。Wnのものは、品物の中からいくつかのものを選ぶことができますか?しかも重さはちょうどweightですか?
weightは具体的にどのように構成されていますか?次の二つの場合があります。
1. Wn-1からweightになります。weight=W 1+W 2+…+Wn=W 1+W 2+…+Wn 1.
2.Wnを加えるとちょうどweightになります。自然にweight=W 1+W 2+…+Wnがあります。
上の二つの状況は一つでも解があるので、Wiをバックパックから消して戻ってweightの値を見ることができます。
一連の逆押しを経て、weightの値は次の3つの場合があります。
1.weightはちょうど0//説明が解ります。
2. weight<0/ありえないので、分かりません。
3.weight>0 and Wがありません ありえない
def knap(weight,weights,n): //weight ,weights ,n
if weight==0:
return True;
if weight<0 or (n<1 and weight>0):
return False;
if knap(weight-weights[n-1],weights,n-1): // 2
print(weights[n-1])
return True
if knap(weight,weights,n-1): // 1
return True
else:
return False
超簡単でしょ!!ダイナミック企画で解決すれば、何十行のコードが必要ですか?これは12行のコードです。簡単明瞭です。以上が本文の全部です。皆さんの勉強に役に立つように、私たちを応援してください。