Fractional Knapsack Problem Python

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)







OUTPUT:

Maximum value we can obtain = 240

CREDITS: https://www.geeksforgeeks.org/fractional-knapsack-problem/