[ナップサック問題 解説] 貪欲法による分数ナップサック問題
ナップサック問題はNP困難な組み合わせ最適化問題として知られているので、今回は品物を0個か1個とれる0-1ナップザック問題を少し改変した分数ナップサック問題の解説をします。当然、この問題はクラス的にはNPではなく、Pクラスとなっています。
n個のアイテムの重みと値が与えられた場合、ナップザックの最大合計値を取得するには、これらのアイテムを容量Wのナップザックに入れる必要があります。容量を超えない範囲で値が最大となるように選択をしますが、0-1ナップサック問題との違いはそのアイテムを分割できるということです。容量を超える場合に、容量がぴったりとなるようにアイテムを分割できます。
分数ナップサック問題におけるアイテムの価値
この問題は
目的：アイテムの価値の最大化
制約：アイテムの重さ
と考えられます。
いま、struct Item = {価値、重さ}という形式で、
Item arr [] = {{60、10}、{100、20 }、{ 120、30 }}というアイテムがW(重さ) = 5０kgという制約でナップサックに詰めるという問題が与えられたとします。
アイテムの価値は各データの第１要素ですが、重さが一様でないので、直接比較ができません。なので、重さあたりの価値を真の価値として考える必要があります。それぞれ重さで割ると、
Item arr[] = {{6},{5},{4}}
のように考えられるので、左のアイテムから順番に制約の重さを超えない範囲でとっていきます。すると、
10kg、20kgのアイテムを詰め、この時点で30kg(アイテムの価値は160)、最後の30kgのアイテムを詰めると制約の50kgを超えてしまうので、分割します。(50kg-30kg)/30kg * 120 = 80 をナップサックに詰めます。
なので答えは160 + 80 = 240となります。
実装
下記のように実装できます。
#include <iostream>
using namespace std;
//Structure for an item which stores weight and correspondig value for Item
struct Item{
int value, weight;
//Constructor
Item(int value, int weight)
{
this->value=value;
this->weight=weight;
}
};
// Comparison function to sort Item according to val/weight ratio
bool cmp(struct Item a, struct Item b){
double r1 = (double)a.value / (double)a.weight;
double r2 = (double)b.value / (double)b.weight;
return r1 > r2;
}
// Main greedy function to solve problem
double fractionalKnapsack(int W, struct Item arr[], int n)
{
// sorting Item on basis of ratio
sort(arr, arr + n, cmp);
// new order of Items with their ratio
for(int i=0; i<n;i++){
cout << arr[i].value << " " << arr[i].weight << " : " << ((double)arr[i].value / arr[i].weight) << endl;
}
int curWeight =0;
double finalvalue = 0.0;
//Looping through all Items
for(int i=0; i < n; i++){
if(curWeight+arr[i].weight <= W){
curWeight += arr[i].weight;
finalvalue += arr[i].value;
}else{
int remain = W - curWeight;
finalvalue += arr[i].value*((double)remain/(double)arr[i].weight);
break;
}
}
return finalvalue;
}
int main(){
int W =50; // Weight of knapsack;
Item arr[] = {{60,10},{100,20},{120,30}};
int n = sizeof(arr) / sizeof(arr[0]);
// Function call
cout << "Maximum value we can obtain = " << fractionalKnapsack(W,arr,n) << endl;
return 0;
}
このように貪欲法で簡易的に実装ができます。