フラクショナルナップサック問題とは？貪欲法による解き方をC++コード付きで解説

フラクショナルナップサック問題とは

フラクショナルナップサック問題では、それぞれ固有の「価値」と「重さ」を持つ品物のリストが与えられます。最大積載重量 W のナップサックに対して、総重量が W を超えない範囲で品物を選び、合計価値を最大化することが目的です。

ナップサック問題には2種類ある

• 0–1ナップサック問題：品物を分割できないため、入れるか入れないかの二択になります。
• フラクショナルナップサック問題：品物を小さく分割できるため、一部だけを詰め込むことも可能です。

本記事では、後者のフラクショナルナップサック問題を取り上げます。この問題は貪欲法（グリーディ法）で必ず最適解が得られることが知られており、時間計算量は O(n log n) です。

入力と出力の例

入力：
最大重量 = 50、価値と重さのペアで表された品物のリスト
{(60, 10), (100, 20), (120, 30)}　※（価値，重さ）

出力：
最大価値：240
重さ 20 と 30 の品物を採用した場合

アルゴリズム

鍵となるのは「価値 ÷ 重さ」（単位重量あたりの価値）という指標です。この値が大きい品物ほど効率が良いので、降順にソートして順番に詰め込んでいきます。ナップサックの残り容量が足りなくなったら、最後の品物は残り容量に応じた割合だけで詰め込みます。

fractionalKnapsack(weight, itemList, n)

入力：ナップサックの最大重量 weight、品物のリスト itemList、品物数 n
出力：達成可能な最大価値

Begin
    itemList を「価値 ÷ 重さ」の比率に基づいて降順にソートする
    currentWeight := 0
    knapsackVal := 0

    リスト中のすべての品物 i について：
        if currentWeight + item[i] の重さ ≤ weight then
            currentWeight := currentWeight + item[i] の重さ
            knapsackVal := knapsackVal + item[i] の価値
        else
            remaining := weight − currentWeight
            knapsackVal := knapsackVal + item[i] の価値 × (remaining ÷ item[i] の重さ)
            ループを抜ける
End

C++での実装例

以下は、上記アルゴリズムをC++で実装した例です。比較関数 cmp によって単位重量あたりの価値が高い順にソートし、先頭から順にナップサックへ詰め込んでいきます。

#include <iostream>
#include <algorithm>
using namespace std;

struct item {
    int value, weight;
};

// 単位重量あたりの価値（value / weight）に基づいて品物 a と b を比較する
bool cmp(struct item a, struct item b) {
    double aRatio = (double)a.value / a.weight;
    double bRatio = (double)b.value / b.weight;
    return aRatio > bRatio;
}

double fractionalKnapsack(int weight, item itemList[], int n) {
    sort(itemList, itemList + n, cmp);   // 比較関数を使って品物リストをソート
    int currWeight = 0;                  // ナップサック内の現在の重量
    double knapsackVal = 0.0;

    for (int i = 0; i < n; i++) {        // すべての品物を順にチェック
        if (currWeight + itemList[i].weight <= weight) { // 容量が十分なら丸ごと詰め込む
            currWeight += itemList[i].weight;
            knapsackVal += itemList[i].value;
        } else {                         // 全体が入り切らない場合は残り容量の分だけ詰め込む
            int remaining = weight - currWeight;
            knapsackVal += itemList[i].value * ((double) remaining / itemList[i].weight);
            break;
        }
    }
    return knapsackVal;
}

int main() {
    int weight = 50;   // ナップサックの最大重量
    item itemList[] = {{60, 10}, {100, 20}, {120, 30}};
    int n = 3;
    cout << "Maximum value: " << fractionalKnapsack(weight, itemList, n);
}

出力結果

Maximum value: 240

なぜ 240 になるのか？

ソート後の優先順位は、単位重量あたりの価値が高い順に (60, 10) → (100, 20) → (120, 30) となります。

1. (60, 10) を丸ごと詰め込む → 重量 10、価値 60
2. (100, 20) を丸ごと詰め込む → 重量 30、価値 160
3. 残り容量は 20 なので、(120, 30) の 2/3（重さ 20 分）だけ詰め込む → 価値 120 × 20/30 = 80

合計価値は 60 + 100 + 80 = 240 となり、これがこの設定における最適解です。

なお、0–1ナップサック問題では品物を分割できないため、この貪欲法は最適解を保証せず、動的計画法などの別の手法が必要になります。一方、フラクショナルナップサック問題は品物を任意に分割できるため、「単位あたり価値の高いものから詰める」という貪欲戦略が常に最適解をもたらすのです。