fractional knapsack 2 Algorithm
The fractional knapsack 2 algorithm is a variation of the classic fractional knapsack problem, which is an optimization problem often used in computer science and economics. The problem involves a knapsack that can carry a limited weight, and a set of items with varying weights and values. The objective of the algorithm is to maximize the total value of items placed in the knapsack, while not exceeding the knapsack's weight limit. The fractional knapsack 2 algorithm differs from the classic version by allowing the items to be divided into fractions, which means that a portion of an item can be taken instead of the whole item.
To solve the fractional knapsack 2 problem, the algorithm first calculates the value-to-weight ratio for each item in the set. The items are then sorted in decreasing order based on their value-to-weight ratios. The algorithm then iteratively selects the item with the highest ratio and adds as much of it as possible to the knapsack without exceeding the weight limit. If the knapsack reaches its weight limit before all items have been considered, the algorithm stops. Otherwise, it continues with the next highest ratio item until the knapsack is full or all items have been considered. This greedy approach ensures that the knapsack is filled with the most valuable items, resulting in the maximum possible value for the given weight limit.
# https://en.wikipedia.org/wiki/Continuous_knapsack_problem
# https://www.guru99.com/fractional-knapsack-problem-greedy.html
# https://medium.com/walkinthecode/greedy-algorithm-fractional-knapsack-problem-9aba1daecc93
from typing import List, Tuple
def fractional_knapsack(
value: List[int], weight: List[int], capacity: int
) -> Tuple[int, List[int]]:
"""
>>> value = [1, 3, 5, 7, 9]
>>> weight = [0.9, 0.7, 0.5, 0.3, 0.1]
>>> fractional_knapsack(value, weight, 5)
(25, [1, 1, 1, 1, 1])
>>> fractional_knapsack(value, weight, 15)
(25, [1, 1, 1, 1, 1])
>>> fractional_knapsack(value, weight, 25)
(25, [1, 1, 1, 1, 1])
>>> fractional_knapsack(value, weight, 26)
(25, [1, 1, 1, 1, 1])
>>> fractional_knapsack(value, weight, -1)
(-90.0, [0, 0, 0, 0, -10.0])
>>> fractional_knapsack([1, 3, 5, 7], weight, 30)
(16, [1, 1, 1, 1])
>>> fractional_knapsack(value, [0.9, 0.7, 0.5, 0.3, 0.1], 30)
(25, [1, 1, 1, 1, 1])
>>> fractional_knapsack([], [], 30)
(0, [])
"""
index = list(range(len(value)))
ratio = [v / w for v, w in zip(value, weight)]
index.sort(key=lambda i: ratio[i], reverse=True)
max_value = 0
fractions = [0] * len(value)
for i in index:
if weight[i] <= capacity:
fractions[i] = 1
max_value += value[i]
capacity -= weight[i]
else:
fractions[i] = capacity / weight[i]
max_value += value[i] * capacity / weight[i]
break
return max_value, fractions
if __name__ == "__main__":
n = int(input("Enter number of items: "))
value = input(f"Enter the values of the {n} item(s) in order: ").split()
value = [int(v) for v in value]
weight = input(f"Enter the positive weights of the {n} item(s) in order: ".split())
weight = [int(w) for w in weight]
capacity = int(input("Enter maximum weight: "))
max_value, fractions = fractional_knapsack(value, weight, capacity)
print("The maximum value of items that can be carried:", max_value)
print("The fractions in which the items should be taken:", fractions)
