小背包问题
列出了物品列表，每件物品都有自己的值和重量。物品可以放在最大重量限制为W的背包中。问题是要找到小于或等于W的重量，并且值要最大化。
背包问题有两种。
0–1背包
小背包
对于0–1背包，不能将物品分成小块，对于小背包，可以将物品分成小块。
在这里，我们将讨论分数背包问题。
该算法的时间复杂度为O（nLogn）。
输入输出
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