fractional knapsack Algorithm
The fractional knapsack algorithm is a greedy algorithm used for solving the classical knapsack problem, where the goal is to maximize the total value of items that can be packed into a knapsack of limited capacity. Unlike the 0/1 knapsack problem, which only allows items to be either taken in their entirety or left behind, the fractional knapsack problem allows items to be broken into smaller fractions, so that a portion of an item can be taken while leaving the rest behind. This makes the problem more amenable to a greedy approach, as the optimal solution can often be found by iteratively selecting the highest-value items until the knapsack is full or there are no more items to consider.
The fractional knapsack algorithm works by first sorting the items based on their value-to-weight ratio, with the highest ratio items being considered first. The algorithm then iteratively selects the items with the highest value-to-weight ratio and adds as much of the item as possible to the knapsack, updating the remaining capacity of the knapsack accordingly. If the knapsack still has capacity remaining after an item has been fully added, the algorithm moves on to the next highest value-to-weight ratio item and repeats the process until the knapsack is full or there are no more items to consider. This greedy approach ensures that the highest-value items are prioritized, allowing for an optimal or near-optimal solution to the problem while maintaining a relatively low computational complexity.
from itertools import accumulate
from bisect import bisect
def fracKnapsack(vl, wt, W, n):
"""
>>> fracKnapsack([60, 100, 120], [10, 20, 30], 50, 3)
240.0
"""
r = list(sorted(zip(vl, wt), key=lambda x: x[0] / x[1], reverse=True))
vl, wt = [i[0] for i in r], [i[1] for i in r]
acc = list(accumulate(wt))
k = bisect(acc, W)
return (
0
if k == 0
else sum(vl[:k]) + (W - acc[k - 1]) * (vl[k]) / (wt[k])
if k != n
else sum(vl[:k])
)
if __name__ == "__main__":
import doctest
doctest.testmod()
