【C++】フラクショナルナップサック問題を貪欲法で解く方法と実装例

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

フラクショナルナップサック問題（Fractional Knapsack Problem）は、それぞれ重み（weight）と価値（value）を持つ複数の品物が与えられ、容量が限られたナップサックに品物を詰め込んで、合計価値を最大化することを目指す古典的な最適化問題です。

この問題の大きな特徴は、品物を途中で分割して詰められるという点です。品物が「全部入れるか、入れないか」の二択しかない0/1ナップサック問題とは異なり、フラクショナル版では「半分だけ入れる」という扱いが許されます。そのため、貪欲法（Greedy Approach）を用いることで、常に最適解を求めることができます。

アルゴリズムの流れ

Begin
  Item構造体の配列を用意する
  価値（value）、重み（weight）、ナップサックの容量（W）、密度（density）を宣言する
  各品物について density ＝ value ÷ weight を計算する
  品物の配列を、密度の降順に並べ替える
  配列の先頭から順に品物を詰め、バッグが満杯になる（総重量が容量Wに達する）まで価値を合計していく
End

C++による実装例

以下は、上記の貪欲法をそのままC++で実装したサンプルプログラムです。品物の価値と重みを入力すると、単位重量あたりの価値（＝価値÷重み）を計算して降順ソートを行い、指定した容量のナップサックに入れられる最大の合計価値を出力します。

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef struct {
    int v;
    int w;
    float d;
} Item;

void input(Item items[], int sizeOfItems) {
    cout << "Enter total " << sizeOfItems << " item's values and weight" << endl;
    for(int i = 0; i < sizeOfItems; i++) {
        cout << "Enter " << i+1 << " V ";
        cin >> items[i].v;
        cout << "Enter " << i+1 << " W ";
        cin >> items[i].w;
    }
}

void display(Item items[], int sizeOfItems) {
    cout << "values: ";
    for(int i = 0; i < sizeOfItems; i++) {
        cout << items[i].v << "\t";
    }
    cout << endl << "weight: ";
    for(int i = 0; i < sizeOfItems; i++) {
        cout << items[i].w << "\t";
    }
    cout << endl;
}

bool compare(Item i1, Item i2) {
    return (i1.d > i2.d);
}

float knapsack(Item items[], int sizeOfItems, int W) {
    float totalValue = 0, totalWeight = 0;
    for(int i = 0; i < sizeOfItems; i++) {
        items[i].d = (float)items[i].v / items[i].w; // 型キャストを実施（vもwもintのため、キャストしないとdが整数になってしまう）
    }
    sort(items, items + sizeOfItems, compare);
    for(int i = 0; i < sizeOfItems; i++) {
        if(totalWeight + items[i].w <= W) {
            totalValue += items[i].v;
            totalWeight += items[i].w;
        } else {
            int wt = W - totalWeight;
            totalValue += wt * items[i].d;
            totalWeight += wt;
            break;
        }
    }
    cout << "Total weight in bag " << totalWeight << endl;
    return totalValue;
}

int main() {
    int W;
    Item items[4];
    input(items, 4);
    cout << "Entered data\n";
    display(items, 4);
    cout << "Enter Knapsack weight\n";
    cin >> W;
    float mxVal = knapsack(items, 4, W);
    cout << "Max value for " << W << " weight is " << mxVal;
}

実行例

たとえば、次の4つの品物とナップサック容量50を入力してみます。

• 品物1 … 価値60／重み10（密度6.0）
• 品物2 … 価値100／重み20（密度5.0）
• 品物3 … 価値120／重み30（密度4.0）
• 品物4 … 価値40／重み20（密度2.0）

Enter total 4 item's values and weight
Enter 1 V 60
Enter 1 W 10
Enter 2 V 100
Enter 2 W 20
Enter 3 V 120
Enter 3 W 30
Enter 4 V 40
Enter 4 W 20
Entered data
values: 60	100	120	40
weight: 10	20	30	20
Enter Knapsack weight
50
Total weight in bag 50
Max value for 50 weight is 240

密度の高い品物から順に、品物1（10kg）と品物2（20kg）を丸ごと詰めると、残り容量は20kgになります。そこで品物3を20kg分だけ分割して詰めることで、価値80を追加できます。結果として、合計重量50kgで最大価値240が得られます。

コードのポイント

• 密度の計算時には (float) への型キャストを行っています。価値vも重みwもint型のため、キャストしないと整数除算となり、正しい密度が求まりません。
• std::sort に比較関数 compare を渡すことで、品物を密度の降順に並べ替えています。
• ループ内では、品物が丸ごと入る場合はそのまま価値を加算し、入りきらない品物に出会った時点で「残り容量×密度」を加算して処理を終了します。それ以降の品物は考慮する必要がありません。
• 計算量はソートが支配的で、全体として O(N log N) です。

なお、品物を分割できない0/1ナップサック問題では貪欲法は最適解を保証できず、動的計画法などの別のアプローチが必要になります。「品物を分割できるかどうか」こそが、両者の本質的な違いだといえるでしょう。