Pythonで分数ナップサック問題を解く！貪欲法による実装と解説

分数ナップサック問題とは

同じ長さを持つ2つのリスト「weights（重さ）」「values（価値）」と、ナップサックの容量を表す数値「capacity」が与えられます。weights[i] と values[i] は、i 番目の品物の重さと価値を表します。容量を超えない範囲で品物を選び、品物の一部だけを持ち運ぶことも可能（その場合、価値は持ち込んだ重さに比例して減少する）という条件のもとで、得られる価値の合計の最大値を求めます。最終的な答えは、小数点以下を切り捨てた整数として返します。

たとえば、入力が weights = [6, 7, 3]、values = [110, 120, 2]、capacity = 10 のとき、出力は 178 になります。

解き方のアルゴリズム（貪欲法）

分数ナップサック問題は、貪欲法を使うことで効率的に最適解を求められます。手順は次のとおりです。

• 結果を保持する変数 res を 0 で初期化します。
• 重さと価値のペアからなるリスト P を作成し、「単位重量あたりの価値（価値 ÷ 重さ）」が大きい順にソートします。
• P の各ペアに対して、以下を繰り返します。
  • capacity が 0 になったら、ループを抜けます。
  • 品物の重さが残り容量より大きい場合は、価値 ×（残り容量 ÷ 重さ）を res に加算し、capacity を 0 にします。
  • 品物の重さが残り容量以下の場合は、価値をすべて res に加算し、capacity からその重さを差し引きます。
• 最後に、res の小数点以下を切り捨てた値を返します。

Pythonでの実装例

class Solution:
    def solve(self, weights, values, capacity):
        res = 0
        for pair in sorted(zip(weights, values), key=lambda x: - x[1]/x[0]):
            if not bool(capacity):
                break
            if pair[0] > capacity:
                res += int(pair[1] / (pair[0] / capacity))
                capacity = 0
            elif pair[0] <= capacity:
                res += pair[1]
                capacity -= pair[0]
        return int(res)

ob = Solution()
weights = [6, 7, 3]
values = [110, 120, 2]
capacity = 10
print(ob.solve(weights, values, capacity))

入力

[6, 7, 3], [110, 120, 2], 10

出力

178

動作の解説

このコードでは、zip() で重さと価値をペア化し、lambda式で「−（価値 ÷ 重さ）」をキーに昇順ソートすることで、単位重量あたりの価値が高い品物から順に処理できるようにしています。

今回の例では、各品物の単位重量あたりの価値は次のようになります。

• 品物0：110 ÷ 6 ≒ 18.33
• 品物1：120 ÷ 7 ≒ 17.14
• 品物2：2 ÷ 3 ≒ 0.67

したがって、まず品物0をまるごとナップサックに入れ（重さ6kg、価値110を獲得）、残り容量は4kgになります。次に品物1（重さ7kg）は全体では入りきらないため、4/7 だけ部分的に入れます。このとき獲得できる価値は 120 × 4/7 ≒ 68.57 となり、int() で切り捨てられて 68 が加算されます。最終的な合計は 110 + 68 = 178 です。

計算量

品物の数を n とすると、ソートに O(n log n)、その後のループ処理に O(n) かかるため、全体の時間計算量は O(n log n) となります。品物を分割できる分数ナップサック問題は、0/1ナップサック問題と異なり動的計画法を使わずとも貪欲法だけで最適解が得られるのが大きな特徴です。