連続ナップサック問題

理論計算機科学において、連続ナップサック問題（分数ナップサック問題とも呼ばれる）は、組み合わせ最適化におけるアルゴリズムの問​​題であり、その目的は、選択された材料の価値を最大化するように選択された異なる材料を分数で容器（「ナップサック」）に詰めることである。^{[1] [2]}これは、容器に入れるアイテムが分割できない古典的なナップサック問題に似ている。ただし、連続ナップサック問題は多項式時間で解ける可能性があるのに対し、古典的なナップサック問題はNP困難である。^{[1]これは、問題の定式化における一見小さな変更が、}計算の複雑さ に大きな影響を与える可能性がある典型的な例である。

連続ナップサック問題または古典的ナップサック問題のインスタンスは、ナップサックの数値容量Wと、各材料のコレクションによって指定できます。各材料には、選択可能な材料の重量w _iとその材料の合計価値v _iという 2 つの数値が関連付けられています。目標は、容量制約に従い 、総利益を最大化しながら 、各材料の量x _i ≤ w _iを選択することです。 古典的ナップサック問題では、各量x _iは 0 またはw _{i の}いずれかである必要があります。連続ナップサック問題では、 x _{i が}0 からw _iまで連続的に変化する点が異なります。^[1]$${\displaystyle \sum _{i}x_{i}\leq W}$$$${\displaystyle \sum _{i}x_{i}v_{i}.}$$

この問題のいくつかの定式化では、変数x _{i を}0から1の範囲に再スケールします。この場合、容量制約はとなり 、目標は総利益を最大化することです。 $${\displaystyle \sum _{i}x_{i}w_{i}\leq W,}$$$${\displaystyle \sum _{i}x_{i}v_{i}.}$$

連続ナップサック問題は、1957年にジョージ・ダンツィグ^{[2] [3]}によって初めて発表された貪欲アルゴリズムによって解くことができる。このアルゴリズムは、単位重量あたりの値によってソートされた順序で材料を考慮する。各材料について、量x _iは可能な限り大きくなるように選択される。

• これまでの選択の合計が容量Wに等しい場合、アルゴリズムはx _i  = 0 に設定します。
• これまでの選択の合計とWの差dがw _iより小さい場合、アルゴリズムはx _i  =  dを設定します。
• 残りのケースでは、アルゴリズムはx _i  =  w _iを選択します。

材料をソートする必要があるため、このアルゴリズムはn個の材料の入力に対してO(nlogn)の時間がかかります。[ 1 ] [ 2  ] しかし^、加重中央値を見つけるアルゴリズムを採用することで、 O ( n )の時間で問題を解くことができます。^[2]