给定n个项目的权重和值，我们需要将这些项目放入容量为W的背包中，以获得背包中的最大总价值。
null
在 0-1背包问题 ，我们不允许破坏物品。我们要么接受整件商品，要么不接受。
输入： 项目（价值、重量）成对 arr[]={60,10}，{100,20}，{120,30} 背包容量，W=50；
输出： 最大可能值=240 以10公斤和20公斤的重量以及2/3的分数 30公斤。因此，总价格将为60+100+（2/3）（120）=240
在里面 分数背包 ，我们可以分解物品，使背包的总价值最大化。在这个问题中，我们可以打破一个项目也被称为分数背包问题。
Input : Same as above Output : Maximum possible value = 240 By taking full items of 10 kg, 20 kg and 2/3rd of last item of 30 kg
A. 蛮力解决方案 将尝试所有可能的子集和所有不同的分数，但这将花费太多的时间。
一 有效解决方案 就是用贪婪的方法。贪婪方法的基本思想是计算每个项目的比值/权重，并根据该比值对项目进行排序。然后把比例最高的项目加起来，直到我们不能把下一个项目作为一个整体加起来，最后尽可能多地加上下一个项目。这永远是这个问题的最佳解决方案。 一个带有我们自己的比较函数的简单代码可以编写如下，请更详细地查看排序函数，排序函数的第三个参数是我们的比较函数，它根据值/重量比按非降序排序项目。 排序后，我们需要循环这些物品，并将它们添加到满足上述标准的背包中。
以下是上述理念的实施情况：
C++
// C/C++ program to solve fractional Knapsack Problem #include <bits/stdc++.h> using namespace std; // Structure for an item which stores weight and // corresponding value of Item struct Item { int value, weight; // Constructor Item( int value, int weight) { this ->value=value; this ->weight=weight; } }; // Comparison function to sort Item according to val/weight // ratio bool cmp( struct Item a, struct Item b) { double r1 = ( double )a.value / ( double )a.weight; double r2 = ( double )b.value / ( double )b.weight; return r1 > r2; } // Main greedy function to solve problem double fractionalKnapsack( int W, struct Item arr[], int n) { // sorting Item on basis of ratio sort(arr, arr + n, cmp); // Uncomment to see new order of Items with their // ratio /* for (int i = 0; i < n; i++) { cout << arr[i].value << " " << arr[i].weight << " : " << ((double)arr[i].value / arr[i].weight) << endl; } */ int curWeight = 0; // Current weight in knapsack double finalvalue = 0.0; // Result (value in Knapsack) // Looping through all Items for ( int i = 0; i < n; i++) { // If adding Item won't overflow, add it completely if (curWeight + arr[i].weight <= W) { curWeight += arr[i].weight; finalvalue += arr[i].value; } // If we can't add current Item, add fractional part // of it else { int remain = W - curWeight; finalvalue += arr[i].value * (( double )remain / ( double )arr[i].weight); break ; } } // Returning final value return finalvalue; } // Driver code int main() { int W = 50; // Weight of knapsack Item arr[] = { { 60, 10 }, { 100, 20 }, { 120, 30 } }; int n = sizeof (arr) / sizeof (arr[0]); // Function call cout << "Maximum value we can obtain = " << fractionalKnapsack(W, arr, n); return 0; } |
JAVA
// Java program to solve fractional Knapsack Problem import java.util.Arrays; import java.util.Comparator; // Greedy approach public class FractionalKnapSack { // function to get maximum value private static double getMaxValue( int [] wt, int [] val, int capacity) { ItemValue[] iVal = new ItemValue[wt.length]; for ( int i = 0 ; i < wt.length; i++) { iVal[i] = new ItemValue(wt[i], val[i], i); } // sorting items by value; Arrays.sort(iVal, new Comparator<ItemValue>() { @Override public int compare(ItemValue o1, ItemValue o2) { return o2.cost.compareTo(o1.cost); } }); double totalValue = 0d; for (ItemValue i : iVal) { int curWt = ( int )i.wt; int curVal = ( int )i.val; if (capacity - curWt >= 0 ) { // this weight can be picked while capacity = capacity - curWt; totalValue += curVal; } else { // item cant be picked whole double fraction = (( double )capacity / ( double )curWt); totalValue += (curVal * fraction); capacity = ( int )(capacity - (curWt * fraction)); break ; } } return totalValue; } // item value class static class ItemValue { Double cost; double wt, val, ind; // item value function public ItemValue( int wt, int val, int ind) { this .wt = wt; this .val = val; this .ind = ind; cost = new Double(( double )val / ( double )wt); } } // Driver code public static void main(String[] args) { int [] wt = { 10 , 40 , 20 , 30 }; int [] val = { 60 , 40 , 100 , 120 }; int capacity = 50 ; double maxValue = getMaxValue(wt, val, capacity); // Function call System.out.println( "Maximum value we can obtain = " + maxValue); } } |
Python3
# Python3 program to solve fractional # Knapsack Problem class ItemValue: """Item Value DataClass""" def __init__( self , wt, val, ind): self .wt = wt self .val = val self .ind = ind self .cost = val / / wt def __lt__( self , other): return self .cost < other.cost # Greedy Approach class FractionalKnapSack: """Time Complexity O(n log n)""" @staticmethod def getMaxValue(wt, val, capacity): """function to get maximum value """ iVal = [] for i in range ( len (wt)): iVal.append(ItemValue(wt[i], val[i], i)) # sorting items by value iVal.sort(reverse = True ) totalValue = 0 for i in iVal: curWt = int (i.wt) curVal = int (i.val) if capacity - curWt > = 0 : capacity - = curWt totalValue + = curVal else : fraction = capacity / curWt totalValue + = curVal * fraction capacity = int (capacity - (curWt * fraction)) break return totalValue # Driver Code if __name__ = = "__main__" : wt = [ 10 , 40 , 20 , 30 ] val = [ 60 , 40 , 100 , 120 ] capacity = 50 # Function call maxValue = FractionalKnapSack.getMaxValue(wt, val, capacity) print ( "Maximum value in Knapsack =" , maxValue) # This code is contributed by vibhu4agarwal |
C#
// C# program to solve fractional Knapsack Problem using System; using System.Collections; class GFG{ // Class for an item which stores weight and // corresponding value of Item class item { public int value; public int weight; public item( int value, int weight) { this .value = value; this .weight = weight; } } // Comparison function to sort Item according // to val/weight ratio class cprCompare : IComparer { public int Compare(Object x, Object y) { item item1 = (item)x; item item2 = (item)y; double cpr1 = ( double )item1.value / ( double )item1.weight; double cpr2 = ( double )item2.value / ( double )item2.weight; if (cpr1 < cpr2) return 1; return cpr1 > cpr2 ? -1 : 0; } } // Main greedy function to solve problem static double FracKnapSack(item[] items, int w) { // Sort items based on cost per units cprCompare cmp = new cprCompare(); Array.Sort(items, cmp); // Traverse items, if it can fit, // take it all, else take fraction double totalVal = 0f; int currW = 0; foreach (item i in items) { float remaining = w - currW; // If the whole item can be // taken, take it if (i.weight <= remaining) { totalVal += ( double )i.value; currW += i.weight; } // dd fraction until we run out of space else { if (remaining == 0) break ; double fraction = remaining / ( double )i.weight; totalVal += fraction * ( double )i.value; currW += ( int )(fraction * ( double )i.weight); } } return totalVal; } // Driver code static void Main( string [] args) { item[] arr = { new item(60, 10), new item(100, 20), new item(120, 30) }; Console.WriteLine( "Maximum value we can obtain = " + FracKnapSack(arr, 50)); } } // This code is contributed by Mohamed Adel |
输出
Maximum value we can obtain = 240
由于主要的耗时步骤是排序，所以整个问题只能在O（n logn）中解决。 本文由Utkarsh Trivedi撰稿。
如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
