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

ナップサック問題には2つのタイプがあります。

• 0 –1ナップザック
• フラクショナルナップザック

0〜1のナップザックの場合、アイテムを小さなピースに分割することはできません。また、フラクショナルナップザックの場合、アイテムを小さなピースに分割することもできます。

ここでは、分数ナップサック問題について説明します。

このアルゴリズムの時間計算量はO（n Log n）です。

入力と出力

Input:
Maximum weight = 50. List of items with value and weight.
{(60, 10), (100, 20), (120, 30)}
Output:
Maximum value: 240
By taking the items of weight 20 and 30

アルゴリズム

fractionalKnapsack(weight, itemList, n)

入力- ナップザックの最大重量、アイテムのリスト、アイテムの数

出力： 得られた最大値。

Begin
   sort the item list based on the ration of value and weight
   currentWeight := 0
   knapsackVal := 0

   for all items i in the list do
      if currentWeight + weight of item[i] < weight then
         currentWeight := currentWeight + weight of item[i]
         knapsackVal := knapsackVal + value of item[i]
      else
         remaining := weight – currentWeight
         knapsackVal “= knapsackVal + value of item[i] * (remaining/weight of item[i])
         break the loop
   done
End

例

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

struct item {
   int value, weight;
};

bool cmp(struct item a, struct item b) {     //compare item a and item b based on the ration of value and weight
   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);      //sort item list using compare function
   int currWeight = 0;        // Current weight in knapsack
   double knapsackVal = 0.0;

   for (int i = 0; i < n; i++) {       //check through all items
      if (currWeight + itemList[i].weight <= weight) {     //when the space is enough for selected item, add it
         currWeight += itemList[i].weight;
         knapsackVal += itemList[i].value;

      }else{       //when no place for whole item, break it into smaller parts
         int remaining = weight - currWeight;
         knapsackVal += itemList[i].value * ((double) remaining / itemList[i].weight);
         break;
      }
   }
   return knapsackVal;
}

int main() {
   int weight = 50;     // Weight of knapsack
   item itemList[] = {{60, 10}, {100, 20}, {120, 30}};
   int n = 3;
   cout << "Maximum value: " << fractionalKnapsack(weight, itemList, n);
}

出力

Maximum value: 240