連続ナップサック問題

理論計算機科学において、連続ナップサック問題（分数ナップサック問題とも呼ばれる）は、組み合わせ最適化におけるアルゴリズムの問​​題であり、その目的は、容器（「ナップサック」）を、選択された材料の価値を最大化するように選択された異なる材料の分数で満たすことである。^{[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]

参考文献

1. Goodrich, Michael T. ; Tamassia, Roberto (2002)、「5.1.1 分数ナップサック問題」、アルゴリズム設計：基礎、分析、およびインターネットの例、John Wiley & Sons、pp.  259– 260。
2. Korte, Bernhard ; Vygen, Jens (2012)、「17.1 分数ナップサックと加重中央値」、組み合わせ最適化：理論とアルゴリズム、アルゴリズムと組み合わせ論、第21巻、Springer、pp.  459– 461、ISBN 9783642244889。
3. Dantzig, George B. (1957)、「離散変数極値問題」、オペレーションズ・リサーチ、5 : 266–277、doi :10.1287/opre.5.2.266  、MR0089098。