# 算法题：如何解决分数背包问题？代码实现

2021年4月9日16:41:43 发表评论 939 次浏览

## 本文概述

arr[] = {{60, 10}, {100, 20}, {120, 30}}

``````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``````

## 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 = 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 ;
}
}

}

//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

# 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``````

``Maximum value we can obtain = 240``