算法题（如何解决分数背包问题（代码实现））

本文概述

C ++
Java
Python3

【算法题（如何解决分数背包问题（代码实现））】给定n个项目的权重和值, 我们需要将这些项目放入容量为W的背包中, 以在背包中获得最大的总价值。
在里面0-1背包问题, 我们不允许破坏物品。我们要么拿走整个物品, 要么不拿走。

输入：
作为(值, 重量)对的项目
arr[] = {{60, 10}, {100, 20}, {120, 30}}
背包容量, W = 50；
输出：取重量10和20公斤的物品以及30公斤的2/3分数, 则最大可能值= 240。因此总价格将为60 + 100 +(2/3)(120)= 240

在分数背包问题中, 我们可以破坏物品以使背包的总价值最大化。我们可以破坏物品的这个问题也称为分数背包问题。

Input : Same as aboveOutput : Maximum possible value = https://www.lsbin.com/240 By taking full items of 10 kg, 20 kg and 2/3rd of last item of 30 kg

一种暴力解决方案将尝试使用所有不同分数的所有可能子集, 但这将花费太多时间。
一个有效的解决方案是使用贪婪的方法。贪婪方法的基本思想是计算每个项目的比率值/权重, 并根据该比率对项目进行排序。然后以比例最高的商品进行添加, 直到我们不能整体添加下一商品, 最后再添加尽可能多的商品。这将永远是解决此问题的最佳方法。
带有我们自己的比较功能的简单代码可以编写如下, 请更仔细地查看sort函数, sort函数的第三个参数是我们的比较功能, 该功能根据值/重量比以非降序对项目进行排序。
排序后, 我们需要遍历这些项目并将其添加到满足上述条件的背包中。
以下是上述想法的实现：
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) : value(value) , 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 = https://www.lsbin.com/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 = https://www.lsbin.com/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 = https://www.lsbin.com/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 = https://www.lsbin.com/FractionalKnapSack.getMaxValue(wt, val, capacity) print ("Maximum value in Knapsack =" , maxValue) # This code is contributed by vibhu4agarwal

输出如下