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

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

本文概述

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 above

Output :
Maximum possible value = 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 = 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

输出如下