小背包问题
列出了物品列表,每件物品都有自己的值和重量。物品可以放在最大重量限制为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