小背包问题

列出了物品列表，每件物品都有自己的值和重量。物品可以放在最大重量限制为W的背包中。问题是要找到小于或等于W的重量，并且值要最大化。

背包问题有两种。

• 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