ナップサック問題

ナップサック問題とは、組合せ最適化における次の問題です。

それぞれに重みと値を持つアイテムのセットが与えられた場合、合計重みが指定された制限以下になり、合計値が可能な限り大きくなるように、コレクションに含めるアイテムを決定します。

この名前は、固定サイズのナップザックに制約され、最も価値のあるアイテムを詰め込まなければならない人が直面する問題に由来しています。この問題は、意思決定者が固定予算または時間制約の下で、分割できない一連のプロジェクトまたはタスクから選択しなければならないリソース割り当てでよく発生します。

ナップザック問題は1世紀以上にわたって研究されており、初期の研究は1897年にまで遡ります。^[1]

ナップザック問題は、原材料を最も無駄なくカットする方法を見つけること、^[2]、投資やポートフォリオの選択、^[3]、資産担保証券化のための資産の選択、^{[4] 、} Merkle-Hellman ^[5]やその他のナップザック暗号システムの鍵生成など、さまざまな分野の現実世界の意思決定プロセスに登場します。

ナップサック アルゴリズムの初期の応用例の 1 つは、受験者がどの質問に答えるかを選択できるテストの作成と採点でした。小規模な例では、受験者にそのような選択肢を提供するのはかなり簡単なプロセスです。たとえば、試験に 10 点の質問が 12 問含まれている場合、受験者は 10 問に答えるだけで最高得点の 100 点を得ることができます。ただし、点数が不均一に分布しているテストでは、選択肢を提供するのが難しくなります。Feuerman と Weiss は、合計 125 点の不均一なテストを学生に提供するシステムを提案しました。学生は、すべての質問に全力で答えるように求められます。ナップサック アルゴリズムは、合計点数が 100 になる問題の可能なサブセットのうち、どのサブセットが各学生に最高得点を与えるかを決定します。^[6]

ストーニーブルック大学アルゴリズムリポジトリの1999年の調査によると、組み合わせアルゴリズムとアルゴリズムエンジニアリングの分野に関連する75のアルゴリズム問題のうち、ナップサック問題は19番目に人気があり、サフィックスツリーとビンパッキング問題に次いで3番目に必要とされていることが示されました。^[7]

最も一般的に解決されている問題は、0-1ナップサック問題であり、これは各種類のアイテムのコピー数を0または1に制限するものです。1から までの番号が付けられたアイテムのセットがあり、それぞれに重量と価値があり、最大重量容量が与えられている場合、 ${\displaystyle x_{i}}$${\displaystyle n}$${\displaystyle n}$${\displaystyle w_{i}}$${\displaystyle v_{i}}$${\displaystyle W}$

最大化する${\displaystyle \sum _{i=1}^{n}v_{i}x_{i}}$

および の対象となります。${\displaystyle \sum _{i=1}^{n}w_{i}x_{i}\leq W}$${\displaystyle x_{i}\in \{0,1\}}$

ここでは、ナップザックに入れるアイテムのインスタンスの数を表します。非公式には、問題は、重量の合計がナップザックの容量以下になるように、ナップザック内のアイテムの値の合計を最大化することです。 ${\displaystyle x_{i}}$${\displaystyle i}$

制限付きナップサック問題( BKP )では、各アイテムが 1 つしかないという制限がなくなりますが、各種類のアイテムのコピー数は最大の非負の整数値に制限されます。 ${\displaystyle x_{i}}$${\displaystyle c}$

最大化する${\displaystyle \sum _{i=1}^{n}v_{i}x_{i}}$

以下に従う${\displaystyle \sum _{i=1}^{n}w_{i}x_{i}\leq W}$${\displaystyle x_{i}\in \{0,1,2,\dots ,c\}.}$

無制限ナップサック問題( UKP )では、各種類のアイテムのコピー数に上限はなく、唯一の制限はそれが非負の整数であるという点を除いて、上記のように定式化できます。 ${\displaystyle x_{i}}$

最大化する${\displaystyle \sum _{i=1}^{n}v_{i}x_{i}}$

以下に従う${\displaystyle \sum _{i=1}^{n}w_{i}x_{i}\leq W}$${\displaystyle x_{i}\in \mathbb {Z} ,\ x_{i}\geq 0.}$

無制限ナップサック問題の一例は、この記事の冒頭に示した図と、その図の説明にある「各書籍が任意の数入手可能な場合」というテキストを使用して示されます。

ナップサック問題は、コンピュータサイエンスの観点から見ると、多くの理由から興味深いものです。

• ナップサック問題の決定問題形式 (重みWを超えずに少なくとも V の値を達成できるか? )はNP 完全であるため、すべての場合に正確かつ高速 (多項式時間) なアルゴリズムは知られていません。
• 与えられた解が最適かどうか（つまり、より大きなVを持つ解が存在しないかどうか）を判断できる多項式アルゴリズムは知られていません。この問題は共NP完全です。
• 動的計画法を使用した疑似多項式時間アルゴリズムがあります。
• 以下に説明するように、擬似多項式時間アルゴリズムをサブルーチンとして使用する、完全な多項式時間近似スキームがあります。
• 実際に発生する多くのケースや、一部の分布からの「ランダムなインスタンス」は、それでも正確に解決できます。

「決定」問題と「最適化」問題の間には関連があり、「決定」問題を解決する多項式アルゴリズムが存在する場合、k の値を増やしながらこのアルゴリズムを繰り返し適用することで、最適化問題の最大値を多項式時間で見つけることができます。一方、アルゴリズムが最適化問題の最適値を多項式時間で見つける場合、このアルゴリズムによって出力されたソリューションの値と k の値を比較することで、決定問題を多項式時間で解決できます。したがって、両方のバージョンの問題は同様の難しさです。

研究文献のテーマの 1 つは、ナップザック問題の「難しい」インスタンスがどのようなものかを特定することです^{[8] [9] [10] 。}または別の見方をすれば、インスタンスの実際の特性によって、最悪の NP 完全動作が示唆するよりもインスタンスがより扱いやすくなる可能性があるかどうかを特定することです^{[11] [12]} 。これらの「難しい」インスタンスを見つける目的は、Merkle–Hellman ナップザック暗号システムなどの公開鍵暗号システムで使用することです。より一般的には、最適化問題のインスタンスの空間構造をよりよく理解することで、特定の問題の研究が進み、アルゴリズムの選択が改善されます。

さらに、ナップサック問題の難しさは入力の形式に依存するという事実も注目に値する。重みと利益が整数として与えられた場合、それは弱NP完全であるが、重みと利益が有理数として与えられた場合は強くNP完全である。^[13]しかし、重みと利益が有理数の場合でも、完全に多項式時間の近似スキームが許容される。

ナップサック問題の NP 困難性は、整数のサイズが問題となる計算モデル (チューリング マシンなど) に関連しています。対照的に、決定木は各決定を 1 つのステップとしてカウントします。Dobkin と Lipton ^[14]は、ナップサック問題の線形決定木、つまり決定ノードがアフィン関数の符号をテストする木に対する下限を示しています。^[15]これは、Steele と Yao によって代数決定木に一般化されました。^[16] 問題の要素が実数または有理数の場合、決定木の下限は、実数の加算、減算、乗算、比較、および除算または剰余 (「床」) を含む命令セットを備えた実際のランダム アクセス マシンモデルにまで拡張されます。 ^[17]このモデルは、テーブルへのインデックスを使用するアルゴリズムを包含するため、代数決定木モデルよりも多くのアルゴリズムをカバーします。ただし、このモデルでは、決定だけでなく、すべてのプログラム ステップがカウントされます。決定木モデルの上限は、マイヤー・アウフ・デア・ハイデ[18]によって与えられ、彼は^、任意のnに対して、 n個の項目を持つ部分集合和問題を解決するO ( n4 )^の深さの線形決定木が存在することを示しました。これは、任意のnに対して問題を解決するアルゴリズムの上限を意味するものではないことに注意してください。 ${\displaystyle {1 \over 2}n^{2}}$

ナップサック問題を解くアルゴリズムはいくつかあり、動的計画法^[19] 、分岐限定法^[20]、または両方のアプローチのハイブリッド^{[11] [21] [22] [23]に基づいている。}

無制限ナップサック問題（UKP ）は、各種類のアイテムのコピー数に制限を設けません。また、ここでは${\displaystyle x_{i}>0}$

${\displaystyle m[w']=\max \left(\sum _{i=1}^{n}v_{i}x_{i}\right)}$

以下に従う${\displaystyle \sum _{i=1}^{n}w_{i}x_{i}\leq w'}$${\displaystyle x_{i}>0}$

には次の特性がある ことに注意してください。${\displaystyle m[w]}$

1. (ゼロ項目の合計、つまり空集合の合計)。 ${\displaystyle m[0]=0\,\!}$

2. 、、ここで は- 番目の種類のアイテム の値です。${\displaystyle m[w]=\max(v_{1}+m[w-w_{1}],v_{2}+m[w-w_{2}],...,v_{n}+m[w-w_{n}])}$${\displaystyle w_{i}\leq w}$${\displaystyle v_{i}}$${\displaystyle i}$

2 番目のプロパティについては詳しく説明する必要があります。このメソッドの実行プロセス中に、重みをどのように取得するのでしょうか。方法は 2 つしかなく、以前の重みは、さまざまなアイテムの合計種類がある場合です (異なるとは、重みと値が完全に同じではないことを意味します)。これらのアイテムの各値と関連する最大値が事前にわかっている場合は、それらを互いに比較して最終的に最大値を取得すれば完了です。 ${\displaystyle w}$${\displaystyle i}$${\displaystyle w-w_{1},w-w_{2},...,w-w_{i}}$${\displaystyle i}$${\displaystyle i}$

ここで、空集合の最大値は 0 とします。から までの結果を集計すると、解が得られます。 それぞれの計算には最大で 個の項目の検査が含まれ、計算するの値は最大で 個あるため、動的計画法の解の実行時間は です。最大公約数で割ると、実行時間を短縮できます。 ${\displaystyle m[0]}$${\displaystyle m[W]}$${\displaystyle m[w]}$${\displaystyle n}$${\displaystyle W}$${\displaystyle m[w]}$${\displaystyle O(nW)}$${\displaystyle w_{1},\,w_{2},\,\ldots ,\,w_{n},\,W}$

P≠NPの場合でも、複雑度はナップサック問題がNP 完全であるという事実と矛盾しません。これは、 とは異なり、 は問題への入力の長さの多項式ではないためです。問題への入力の長さは、 のビット数に比例し、それ自体には比例しません。ただし、この実行時間は擬似多項式であるため、ナップサック問題 (の決定バージョン) は弱 NP 完全問題になります。 ${\displaystyle O(nW)}$${\displaystyle W}$${\displaystyle n}$${\displaystyle W}$${\displaystyle W}$${\displaystyle \log W}$${\displaystyle W}$

0-1 ナップサック問題に対する同様の動的プログラミング ソリューションも、擬似多項式時間で実行されます。 は厳密に正の整数であると仮定します。 を、(最初のアイテム)までのアイテムを使用して と等しいかそれ以下の重みで達成できる最大値として定義します。 ${\displaystyle w_{1},\,w_{2},\,\ldots ,\,w_{n},\,W}$${\displaystyle m[i,w]}$${\displaystyle w}$${\displaystyle i}$${\displaystyle i}$

再帰的に次のように定義できます。(定義A)${\displaystyle m[i,w]}$

• ${\displaystyle m[0,\,w]=0}$
• ${\displaystyle m[i,\,w]=m[i-1,\,w]}$(新しいアイテムが現在の重量制限を超えている場合)${\displaystyle w_{i}>w\,\!}$
• ${\displaystyle m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_{i}]+v_{i})}$もし。${\displaystyle w_{i}\leqslant w}$

解は を計算することで求められます。これを効率的に行うために、以前の計算結果を保存するテーブルを使用できます。 ${\displaystyle m[n,W]}$

以下は動的プログラムの疑似コードです。

// 入力:
// 値（配列 v に格納）
// 重み（配列 w に格納）
// 異なる項目の数 (n)
// ナップザック容量 (W)
// 注意: 配列 "v" と配列 "w" には、インデックス 1 から始まるすべての関連する値が格納されると想定されます。

配列m [ 0. . n , 0. . W ];  
jが0からWまでの場合、以下を実行します。      
    m [ 0 , j ] := 0   
1からnまでのiに対して以下を実行します。      
    m [ i , 0 ] := 0   

1からnまでのiに対して以下を実行します。      
    jが1からWまでの場合、以下を実行します。      
        w [ i ] > jの場合:    
            m [ i , j ] := m [ i -1 , j ]    
        それ以外：
            m [ i , j ] := max ( m [ i -1 , j ], m [ i -1 , j - w [ i ]] + v [ i ])        

したがって、このソリューションは時間と空間で実行されます。(値 m[n,W] のみが必要な場合は、配列 "m" の最新の 2 行を格納するために必要なメモリ量が O(W) になるようにコードを変更できます。) ${\displaystyle O(nW)}$${\displaystyle O(nW)}$

しかし、もう 1 つか 2 つ進めば、メソッドは から までの間に実行されることがわかります。定義Aから、アイテムの数と選択したアイテム自体が固定されている場合は、すべての重みを計算する必要がないことがわかります。つまり、上記のプログラムは、重みが 0 から W に頻繁に変化するため、必要以上に計算しています。この観点から、このメソッドを再帰的に実行するようにプログラムできます。 ${\displaystyle O(nW)}$${\displaystyle O(2^{n})}$

// 入力:
// 値（配列 v に格納）
// 重み（配列 w に格納）
// 異なる項目の数 (n)
// ナップザック容量 (W)
// 注意: 配列 "v" と配列 "w" には、インデックス 1 から始まるすべての関連する値が格納されると想定されます。

値[ n , W ]を定義する  

すべての値を初期化する[ i , j ] = -1     

m := ( i , j )を定義// 関数 m を定義して、次の条件で取得できる最大値を表すようにします: 最初の i 個のアイテムを使用し、合計重量制限は j です          
{
    i == 0またはj <= 0の場合:        
        値[ i , j ] = 0   
        戻る

    if ( value [ i -1 , j ] == -1 ) then : // m[i-1, j] が計算されていないので、関数 m を呼び出す必要があります。          
        m ( i -1 , j ) 

    if w [ i ] > j then : // アイテムはバッグに収まりきらない                          
        値[ i , j ] =値[ i -1 , j ]    
    それ以外： 
        if ( value [ i -1 , j - w [ i ]] == -1 ) then : // m[i-1,jw[i]] が計算されていないので、関数 m を呼び出す必要があります。          
            m ( i -1 、j - w [ i ]) の 
        値[ i , j ] =最大値(値[ i -1 , j ],値[ i -1 , j - w [ i ]] + v [ i ])       
}

m ( n , W )を実行する  

たとえば、異なるアイテムが 10 個あり、重量制限が 67 であるとします。したがって、 上記の方法を使用して を計算すると、 を生成する呼び出しを除いて、次のようになります。 $${\displaystyle {\begin{aligned}&w[1]=23,w[2]=26,w[3]=20,w[4]=18,w[5]=32,w[6]=27,w[7]=29,w[8]=26,w[9]=30,w[10]=27\\&v[1]=505,v[2]=352,v[3]=458,v[4]=220,v[5]=354,v[6]=414,v[7]=498,v[8]=545,v[9]=473,v[10]=543\\\end{aligned}}}$$${\displaystyle m(10,67)}$${\displaystyle m(i,j)=0}$$${\displaystyle {\begin{aligned}&m(10,67)=1270\\&m(9,67)=1270,m(9,40)=678\\&m(8,67)=1270,m(8,40)=678,m(8,37)=545\\&m(7,67)=1183,m(7,41)=725,m(7,40)=678,m(7,37)=505\\&m(6,67)=1183,m(6,41)=725,m(6,40)=678,m(6,38)=678,m(6,37)=505\\&m(5,67)=1183,m(5,41)=725,m(5,40)=678,m(5,38)=678,m(5,37)=505\\&m(4,67)=1183,m(4,41)=725,m(4,40)=678,m(4,38)=678,m(4,37)=505,m(4,35)=505\\&m(3,67)=963,m(3,49)=963,m(3,41)=505,m(3,40)=505,m(3,38)=505,m(3,37)=505,m(3,35)=505,m(3,23)=505,m(3,22)=458,m(3,20)=458\\&m(2,67)=857,m(2,49)=857,m(2,47)=505,m(2,41)=505,m(2,40)=505,m(2,38)=505,m(2,37)=505,m(2,35)=505,m(2,29)=505,m(2,23)=505\\&m(1,67)=505,m(1,49)=505,m(1,47)=505,m(1,41)=505,m(1,40)=505,m(1,38)=505,m(1,37)=505,m(1,35)=505,m(1,29)=505,m(1,23)=505\\\end{aligned}}}$$

さらに、再帰を分割してツリーに変換することができます。次に、いくつかの葉を切り取り、並列コンピューティングを使用してこのメ​​ソッドの実行を高速化できます。

アイテムの合計値だけでなく、アイテムの実際のサブセットを見つけるには、上記の関数を実行した後にこれを実行できます。

/**
* 最適なナップザックのアイテムのインデックスを返します。
* i: 1からiまでのアイテムをナップザックに入れることができます
* j: ナップザックの最大重量
*/
関数ナップサック( i : int , j : int ) : Set <int> {​​      
    i == 0の場合:    
        戻る{} 
    m [ i , j ] > m [ i -1 , j ]の場合:      
        戻り値{ i } ∪ナップサック( i -1 , j - w [ i ])    
    それ以外：
        ナップサック( i -1 , j )を返す  
}

ナップザック( n , W ) 

0-1 ナップザックの別のアルゴリズムは 1974 年に発見され^{[24] 、}暗号化における同様の名前のアルゴリズムとの類似性から「meet-in-the-middle」と呼ばれることもありますが、異なる項目の数に対して指数関数的ですが、がnに比べて大きい場合は DP アルゴリズムよりも適している可能性があります。特に、が非負であるが整数でない場合は、スケーリングと丸め (つまり、固定小数点演算を使用) によって動的計画法アルゴリズムを使用できますが、問題が正しい答えに到達するために小数桁の精度を必要とする場合は、を でスケーリングする必要があり、DP アルゴリズムにはスペースと時間が必要になります。 ${\displaystyle W}$${\displaystyle w_{i}}$${\displaystyle d}$${\displaystyle W}$${\displaystyle 10^{d}}$${\displaystyle O(W10^{d})}$${\displaystyle O(nW10^{d})}$

アルゴリズムMeet-in-the-middle は、入力:重みと値を持つアイテムのセット
    です。
    出力:サブセットの最大の組み合わせ値です。

    集合{1... n }をほぼ同じ大きさの2つの集合AとBに分割する
    各セットのすべてのサブセットの重みと値を計算する

    Aの 各サブセットについて、合計重みがW未満となる最大値を持つB
        のサブセットを見つけます。 

    これまでに見られた最大の合計値を追跡する

このアルゴリズムは空間を必要とし、ステップ 3 の効率的な実装 (たとえば、B のサブセットを重みでソートし、B のサブセットのうち、より大きいか等しい他のサブセットよりも重みが大きいものを破棄し、バイナリ検索を使用して最適な一致を見つける) により、実行時間は になります。暗号のmeet in the middle 攻撃と同様に、これは単純なブルート フォース手法 ( のすべてのサブセットを調べる) の実行時間を改善しますが、定数ではなく指数空間を使用するというコストがかかります ( baby-step giant-stepも参照)。Schroeppel と Shamir の Algorithm for Subset Sum からの洞察を使用した、meet-in-the-middle アルゴリズムの現在の最先端の改良は、結果として Knapsack のランダム化アルゴリズムを提供します。このアルゴリズムは(多項式因数まで) 実行時間を維持し、空間要件を まで削減します( ^[25]系 1.4 を参照)。対照的に、最もよく知られている決定論的アルゴリズムは、わずかに悪い という空間計算量で時間内に実行されます。^[26]${\displaystyle O(2^{n/2})}$${\displaystyle O(n2^{n/2})}$${\displaystyle O(n2^{n})}$${\displaystyle \{1...n\}}$${\displaystyle O^{*}(2^{n/2})}$${\displaystyle O^{*}(2^{0.249999n})}$${\displaystyle O^{*}(2^{n/2})}$${\displaystyle O^{*}(2^{n/4})}$

ほとんどの NP 完全問題の場合、最適でなくても実行可能なソリューションを見つければ十分です。ただし、近似には、見つかったソリューションの値と最適ソリューションの値の差が保証されていることが望ましいです。

多くの有用だが計算が複雑なアルゴリズムと同様に、解を近似するアルゴリズムの作成と分析に関する研究が盛んに行われてきました。ナップサック問題はNP困難ではあるものの、指定された程度まで近似できるアルゴリズムの集合の1つです。つまり、この問題には多項式時間近似スキームがあります。正確に言うと、ナップサック問題には完全多項式時間近似スキーム（FPTAS）があります。^[27]

ジョージ・ダンツィグは、無限ナップサック問題を解決するために貪欲 近似アルゴリズムを提案した。 ^[28]彼のバージョンでは、重量単位あたりの価値 の降順でアイテムをソートする。次に、最初の種類のアイテムをできるだけ多くコピーして、袋にスペースがなくなるまで袋に挿入する。各種類のアイテムの供給量が無制限であると仮定すると、が袋に収まるアイテムの最大値である場合、貪欲アルゴリズムは少なくとも の値を達成することが保証されます。 ${\displaystyle v_{1}/w_{1}\geq \cdots \geq v_{n}/w_{n}}$${\displaystyle m}$${\displaystyle m/2}$

各種類のアイテムの供給が限られている有界問題の場合、上記のアルゴリズムは最適とはほど遠い可能性があります。それでも、簡単な変更でこのケースを解決できます。簡単にするために、すべてのアイテムが個別に袋に収まると仮定します (すべての に対して)。アイテムをできるだけ貪欲に詰め込むことで、つまりとなるようにソリューションを構築します。さらに、収まらなかった最初のアイテムを含む2 番目のソリューションを構築します。 は問題のLP 緩和の上限を提供するため、セットの 1 つは少なくとも の値を持つ必要があります。したがって、 と のうちより良い値を持つものを返して、 -近似を取得します。 ${\displaystyle w_{i}\leq W}$${\displaystyle i}$${\displaystyle S_{1}}$${\displaystyle S_{1}=\left\{1,\ldots ,k\right\}}$${\displaystyle k=\textstyle \max _{1\leq k'\leq n}\textstyle \sum _{i=1}^{k'}w_{i}\leq W}$${\displaystyle S_{2}=\left\{k+1\right\}}$${\displaystyle S_{1}\cup S_{2}}$${\displaystyle m/2}$${\displaystyle S_{1}}$${\displaystyle S_{2}}$${\displaystyle 1/2}$

^{平均性能は、誤差率[29]}で分布の最適解に収束することが示される。${\displaystyle n^{-1/2}}$

ナップサック問題に対する完全多項式時間近似スキーム(FPTAS) は、問題に多項式時間解法が知られていない理由は、アイテムに関連付けられた利益が制限されていないためであるという事実を利用しています。利益値のいくつかの最下位桁を切り捨てると、それらは多項式と 1/ε によって制限されます。ここで、ε は解の正確さの制限です。この制限は、アルゴリズムが最適解の係数 (1-ε) 以内の正確な解を多項式時間で見つけることができることを意味します。^[27]

アルゴリズムFPTASは 
    入力される: ε ∈ (0,1]値、重み
    
           で指定されたn個の項目のリストAの出力: S' FPTASソリューション${\displaystyle v_{i}}$

    P := max   // アイテムの最高値${\displaystyle \{v_{i}\mid 1\leq i\leq n\}}$
    K := ε${\displaystyle {\frac {P}{n}}}$

    iから1まで、do
          := end for${\displaystyle v'_{i}}$${\displaystyle \left\lfloor {\frac {v_{i}}{K}}\right\rfloor }$
    

    上記の動的プログラムの値
を使用して、解S'を返します。${\displaystyle v'_{i}}$

定理:上記のアルゴリズムによって計算された集合はを満たします。ここで は最適解です。 ${\displaystyle S'}$${\displaystyle \mathrm {profit} (S')\geq (1-\varepsilon )\cdot \mathrm {profit} (S^{*})}$${\displaystyle S^{*}}$

量子近似最適化アルゴリズム（QAOA）は、量子計算を使用してナップサック問題を解決するために使用することができ、問題のハミルトニアンを最小化します。ナップサックハミルトニアンは、制約条件をペナルティ項とともに問題のコスト関数に埋め込むことによって構築されます。 ^[30]ここで、はケース固有の微調整によって決定されるペナルティ定数です。 $${\displaystyle {H}=-\sum _{i=1}^{n}v_{i}x_{i}+P\left(\sum _{i=1}^{n}w_{i}x_{i}-W\right)^{2},}$$${\displaystyle P}$

無制限ナップサック問題を解くのは、必要のないアイテムを捨てることで簡単になります。 与えられたアイテム について、合計重量が の重量より小さく、合計値が の値より大きいアイテムのセットを見つけることができたとします。を含む潜在的なソリューションは、セット に置き換えることで常に改善できるため、 は最適ソリューションに現れません。 したがって、 番目のアイテムを完全に無視できます。 このような場合、はを支配すると言われます。 ( のアイテムをすでに使い果たしている可能性があるため、これは制限付きナップサック問題には適用されないことに注意してください。) ${\displaystyle i}$${\displaystyle J}$${\displaystyle i}$${\displaystyle i}$${\displaystyle i}$${\displaystyle i}$${\displaystyle i}$${\displaystyle J}$${\displaystyle i}$${\displaystyle J}$ ${\displaystyle i}$${\displaystyle J}$

優位関係を見つけることで、探索空間のサイズを大幅に縮小することができます。優位関係にはいくつかの種類があり、^[11]すべて次の形式の不等式を満たします。

${\displaystyle \qquad \sum _{j\in J}w_{j}\,x_{j}\ \leq \alpha \,w_{i}}$、そして一部の人にとっては${\displaystyle \sum _{j\in J}v_{j}\,x_{j}\ \geq \alpha \,v_{i}\,}$${\displaystyle x\in Z_{+}^{n}}$

ここで 、 および です。ベクトルはの各メンバーのコピー数を表します。 ${\displaystyle \alpha \in Z_{+}\,,J\subsetneq N}$${\displaystyle i\not \in J}$${\displaystyle x}$${\displaystyle J}$

集団的支配

内のアイテムのいくつかの組み合わせの合計重みがw _iより小さく、それらの合計値がv _iより大きい場合、 -番目のアイテムは によって集合的に支配され、 と書き表されます。正式には、およびいくつかの に対して、すなわち となります。この支配を検証することは計算上困難なので、動的計画法のアプローチでのみ使用できます。実際、これは、、、およびアイテムが に制限されている、より小さなナップサック決定問題を解くことと同等です。${\displaystyle i}$${\displaystyle J}$${\displaystyle i\ll J}$${\displaystyle J}$${\displaystyle \sum _{j\in J}w_{j}\,x_{j}\ \leq w_{i}}$${\displaystyle \sum _{j\in J}v_{j}\,x_{j}\ \geq v_{i}}$${\displaystyle x\in Z_{+}^{n}}$${\displaystyle \alpha =1}$${\displaystyle V=v_{i}}$${\displaystyle W=w_{i}}$${\displaystyle J}$

閾値優位性

のいくつかのコピーが によって支配されている場合、番目のアイテムは によって閾値支配され、 と書き表されます。正式には、であり、いくつかのおよびに対して です。これは集団的支配の一般化であり、^[19]で初めて導入され、EDUK アルゴリズムで使用されています。このような最小の はアイテム の閾値を定義し、 と書き表されます 。この場合、最適解には のコピーが最大で含まれます。${\displaystyle i}$${\displaystyle J}$${\displaystyle i\prec \prec J}$${\displaystyle i}$${\displaystyle J}$${\displaystyle \sum _{j\in J}w_{j}\,x_{j}\ \leq \alpha \,w_{i}}$${\displaystyle \sum _{j\in J}v_{j}\,x_{j}\ \geq \alpha \,v_{i}\,}$${\displaystyle x\in Z_{+}^{n}}$${\displaystyle \alpha \geq 1}$${\displaystyle \alpha }$${\displaystyle i}$${\displaystyle t_{i}=(\alpha -1)w_{i}}$${\displaystyle \alpha -1}$${\displaystyle i}$

多重優位

番目の項目は、 がのいくつかのコピーによって支配されている場合、と表記される単一の項目 によって多重に支配されます。正式には、であり、ある、すなわちに対して です。この優位性は比較的簡単に検出できるため、前処理中に効率的に使用できます。${\displaystyle i}$${\displaystyle j}$${\displaystyle i\ll _{m}j}$${\displaystyle i}$${\displaystyle j}$${\displaystyle w_{j}\,x_{j}\ \leq w_{i}}$${\displaystyle v_{j}\,x_{j}\ \geq v_{i}}$${\displaystyle x_{j}\in Z_{+}}$${\displaystyle J=\{j\},\alpha =1,x_{j}=\lfloor {\frac {w_{i}}{w_{j}}}\rfloor }$

モジュールの優位性

を最良の項目、すなわちすべての に対してとします。これは値の密度が最大となる項目です。が のプラス複数コピーによって支配されている場合、- 番目の項目は単一の項目 によってモジュラ支配され、 と書き表されます。正式には、であり、 すなわち です。${\displaystyle b}$${\displaystyle {\frac {v_{b}}{w_{b}}}\geq {\frac {v_{i}}{w_{i}}}\,}$${\displaystyle i}$${\displaystyle i}$${\displaystyle j}$${\displaystyle i\ll _{\equiv }j}$${\displaystyle i}$${\displaystyle j}$${\displaystyle b}$${\displaystyle w_{j}+tw_{b}\leq w_{i}}$${\displaystyle v_{j}+tv_{b}\geq v_{i}}$${\displaystyle J=\{b,j\},\alpha =1,x_{b}=t,x_{j}=1}$