ブランチとバインドされたメソッドを持つ変更されたナップザック

Question

したがって、次のような問題があります。オブジェクトのNカテゴリのセットがあります。各カテゴリには、それぞれ指定された値と重みを持つMオブジェクトがあります。重みが< =ある与えられた容量Wとなるように、各カテゴリから1つのオブジェクトを選択する必要があり、値は最大です。タスクは、branchおよびboundsメソッドを使用して解決する必要があります。私はこの方法がこの状況でどのように動作するはずであるか理解するのに苦労しています。それを私に説明してもらえますか？

Answer 1

アルゴリズムが何をすべきかの簡単な例。

あなたには、[(weight, value)]= [(3, 5),(8, 10),(1, 2),(4, 5)]の4つのアイテムがあります。 まず重量= [(1, 2),(12, 20),(4, 5),(9, 10)] あたりが値にそれらを並べ替えると、最大重量はあなたのいずれかの広告や、アイテムをドロップし、ツリーを作る最初の項目から始まる16

です。 ツリーの各レベルで、重みと、値と、まだ3つに残っている値を計算します。ブランチのleft + valueの値が見つかった最大値よりも小さい場合は、そのブランチを閉じます。体重が声を上回っている場合は、枝を閉じます。それがどのように動作するかをの概略以下

。

         (value)   (0) 
             (weight)  (0) 
             (value left) (37) 
               add   drop 
    (1,2)         <-------  ------>  
            (2)         (0) 
            (1)         (0) 
            (35)         (35) 
    (20,12)   --------------------------------------------------------------- 
         (22)     (2)    (20)    (0) 
         (13)     (1)    (12)    (0) 
         (15)     *(15)    (15)    *(15) 
    (4,5)  ----------------------------------------------------------------------- 
        (27)  (22)       (25)   (20) 
        (17)  (13)       (16)   (12) 
       **(10)  (10)       (10)   (10) 
    (9,10)  --------------------------------------------------------------------------- 
          (31) (20)     (35) (25) (30) (20) 
          (22) (13)     (25) (16) (21) (12) 
          **(0) (0)     **(0) (0) **(0) (0) 
                   win 

*分岐が原因値+値は、ツリー内<、最大値を左こと

**分岐が原因量が声を出して重量以上であることを閉じているために閉じられます。

この方法の利点は、ブルートフォース方式と比較して計算量を削減できることです。重量あたりの価値が最も高いアイテムを開始することによって、ブランチをすぐに終了して計算時間を短縮する可能性が非常に高いです。

うまくいけば、これは役に立ちます