鏁版嵁緇撴瀯絎簲绔犲～絀洪鍙?qiáng)绛旀[13]_璺ㄨ€冪綉

1. 璁炬湁涓€涓儗鍖呭彲浠ユ斁鍏ョ殑鐗╁搧閲嶉噺涓?/span>S錛岀幇鏈?/span>n浠剁墿鍝侊紝閲嶉噺鍒嗗埆涓?/span>W1錛?/span>W2錛?/span>...錛?/span>Wn銆傞棶鑳藉惁浠庤繖n浠剁墿鍝佷腑閫夋嫨鑻ュ共浠舵斁鍏ヨ儗鍖咃紝浣垮緱鏀懼叆鐨勯噸閲忎箣鍜屾濂芥槸S銆傝甯冨皵鍑芥暟Knap(S錛?/span>n)琛ㄧず鑳屽寘闂鐨勮В錛?/span>Wi(i=1,2,...錛?/span>n)鍧囦負(fù)姝ｆ暣鏁幫紝騫跺凡欏哄簭瀛樺偍鍦板湪鏁扮粍W涓€傝鍦ㄤ笅鍒楃畻娉曠殑涓嬪垝綰垮濉┖錛屼嬌鍏舵紜眰瑙ｈ儗鍖呴棶棰樸€?/span>

銆€銆€Knap(S錛?/span>n)

銆€銆€鑻?/span>S=0

銆€銆€鍒?/span>Knap鈫?/span>true

銆€銆€鍚﹀垯鑻ワ紙S<0錛夋垨(S>0涓?/span>n<1)

銆€銆€鍒?/span>Knap鈫?/span>false

銆€銆€鍚﹀垯鑻?/span>Knap(1) , _=true

銆€銆€鍒?/span>print(W[n])錛?/span>Knap 鈫?/span>true

銆€銆€鍚﹀垯 Knap鈫?/span>Knap(2) _ , _

銆€銆€銆愬北涓滃伐涓氬ぇ瀛?/span>1996 浜旓紙10鍒嗭級1998 浜屻€?/span>1 錛?/span>4鍒嗭級銆?/span>

銆€銆€銆愬弬鑰冪瓟妗堛€?/span>

銆€銆€鑻ョn浠剁墿鍝佽兘鏀懼叆鑳屽寘錛屽垯闂鍙樹負(fù)鑳藉惁鍐嶄粠n-1浠剁墿鍝佷腑閫夊嚭鑻ュ共浠舵斁鍏ヨ儗鍖咃紙榪欐椂鑳屽寘鍙斁鍏ョ墿鍝佺殑閲嶉噺鍙樹負(fù)s-w[n]錛夈€傝嫢絎?/span>n浠剁墿鍝佷笉鑳芥斁鍏ヨ儗鍖咃紝鍒欒€冭檻浠?/span>n-1浠剁墿鍝侀€夎嫢騫蹭歡鏀懼叆鑳屽寘錛堣繖鏃惰儗鍖呭彲鏀懼叆鐗╁搧浠嶄負(fù)s錛夈€傝嫢鏈€緇?/span>s=0,鍒欐湁涓€瑙ｏ紱鍚﹀垯錛岃嫢s<0鎴栬櫧鐒?/span>s>0浣嗙墿鍝佹暟n<1,鍒欐棤瑙ｃ€?/span>

銆€銆€錛?/span>1錛?/span>s-w[n],n-1 //Knap(s-w[n],n-1)=true

銆€銆€錛?/span>2錛?/span>s,n-1 // Knap鈫?/span>Knap(s,n-1)