スタック応用のリュックサック問題(Python版)

スタック応用のリュックサック問題
リュックサックの问题の说明:1つのリュックサックの中で重量のweightの物品を入れることができて、既存のn件の物品の集合s、その中の物品の重量は别にw 0、w 1、...、wn-1.問題は、その中からいくつかの品物を選ぶことができるかどうかで、その重量の和はちょうどweightに等しいので、もし存在するならばこのリュックサックの問題が解けていることを説明して、さもなくば解けません.
 

再帰方式を用いて

を解く.

 1 def knap_rec(weight,wlist,n) :
 2     if weight == 0 :
 3         return True
 4     if weight < 0 or (weight >0 and n < 1) :
 5         return False 
 6     if knap_rec(weight - wlist[n-1],wlist,n-1) :
 7         print("Item" + str(n) + ":" , wlist[n-1])
 8         return True
 9     if knap_rec(weight,wlist,n-1) :
10         return True
11     else :
12         return False

 
 
 

スタック定義非再帰方式を用いて解く、

 
 
 
 
 
 
転載先:https://www.cnblogs.com/zlsgh/p/9580230.html