本文概述
- C ++
- Java
- Python3
在里面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
输出如下
Maximum value we can obtain = 240
由于主要的时间步骤是排序, 因此整个问题只能在O(n log n)中解决。
本文由Utkarsh Trivedi提供。
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。
推荐阅读
- AngularJS angular.uppercase()函数用法示例
- 如何使用JavaScript获取父级的子级元素()
- CSS基本语法和选择器用法示例
- SDE1 FTE/6M实习生的Amazon面试体验(校园内)
- 算法设计(用信号量来解决哲学家问题)
- jQuery jQuery.fx.interval属性用法示例
- JavaScript数组valueOf()方法使用示例
- PHP Ds\Map __construct()函数用法示例详解
- 亚马逊面试体验分享| SDE-1的校园内