部分背包问题(factional knapsack)
给定一组物品,每种物品都有自己的重量和价值,物品可分割,也就是可以放某物品的一部分,类似米、面、油等商品。在限定的总重量内,我们如何选择,才能使得物品的总价格最高。
假设商店中有 4种商品,它们各自的重量和价值是:
商品 1:重量 1 斤,价值5 元;
商品 2:重量 2 斤,价值 12 元;
商品 3:重量 3 斤,价值 12 元;
商品 4:重量4斤,价值16元。
对于每件商品,顾客可以购买商品的一部分(可再分)。一个小偷想到商店行窃,他的背包最多只能装 5斤的商品,如何选择才能获得最大的收益呢?
用贪心算法解决此问题的思路是:计算每个商品的收益率(收益/重量),优先选择收益率最大的商品。
方法一:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 | /**************************************************************** * Description: C++ program to solve fractional Knapsack Problem * Author: Alex Li * Date: 2022-05-08 17:26:59 * LastEditTime: 2023-06-15 17:09:17 ****************************************************************/ #include <iostream> using namespace std; // Structure for an item which stores weight & corresponding value of Item struct Item { int value, weight; }; // Comparison function to sort Item // according to val/weight ratio bool cmp(struct Item a, struct Item b){ double r1 = (double)a.value / a.weight; double r2 = (double)b.value / b.weight; return r1 > r2; } // Main greedy function to solve problem double fractionalKnapsack(struct Item arr[],int N, int size){ // Sort Item on basis of ratio sort(arr, arr + size, cmp); // Current weight in knapsack int curWeight = 0; // Result (value in Knapsack) double finalvalue = 0.0; // Looping through all Items for (int i = 0; i < size; i++) { // If adding Item won't overflow, add it completely if (curWeight + arr[i].weight <= N) { curWeight += arr[i].weight; finalvalue += arr[i].value; } // If we can't add current Item,add fractional part of it else { int remain = N - curWeight; finalvalue += arr[i].value* ((double)remain/ arr[i].weight); break; } } // Returning final value return finalvalue; } // Driver Code int main(){ // Weight of knapsack int N = 60; // Given weights and values as a pairs Item arr[] = { { 100, 10 }, { 280, 40 }, { 120, 20 }, { 120, 24 } }; int size = sizeof(arr) / sizeof(arr[0]); // Function Call cout << "Maximum profit earned = "<< fractionalKnapsack(arr, N, size); return 0; } |
方法二:
在结构体当中加了ratio元素
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | /**************************************************************** * Description: C++ program to solve fractional Knapsack Problem 实现部分背包问题 * Author: Alex Li * Date: 2022-04-23 19:34:18 * LastEditTime: 2023-06-15 17:04:45 ****************************************************************/ #include <iostream> #include <algorithm> using namespace std; struct article{ float weight; int value; float ratio; }; bool compare( article a, article b){ if(a.ratio > b.ratio) return true; else return false; } int main(){ int knapsack_weight,article_number; float result=0; cout<<"please input knapsack weight and article number: "; cin>>knapsack_weight>>article_number; struct article *p; p=new article[article_number]; cout<<"please input "<<article_number<<" weight and "<<article_number<<" value of items: "; for (int i = 0; i < article_number; i++){ cin>>p[i].weight>>p[i].value; p[i].ratio=p[i].value/p[i].weight; } sort(p,p+article_number,compare); for (int i = 0; i < article_number; i++){ if(p[i].weight<=knapsack_weight){ knapsack_weight=knapsack_weight-p[i].weight; result=result+p[i].value; } else{ result=result+knapsack_weight*p[i].ratio; break; } } cout<<result; } |
洛谷:P2240