Knapsack Problem
You have a knapsack with a weight limit, and you want to maximize the value of the items you can fit into the knapsack without exceeding its weight capacity.
Example:
A (8kg, 40$)
B (5kg, 30$)
C (3kg, 20$)
D (2kg, 15$)
Knapsack Capacity: 12
Solution:
(D) 2kg, 15$ + (C) 3kg, 6.6$ + (B) 5kg, 6$ + (A) 2kg, 5$ = 12kg, 75$
Fractions
The solution should maximize the total value while respecting the knapsack's weight limit. In the fractional knapsack problem, fractions can be real numbers. 1. Calculate value-to-weight ratio for each item. 2. Sort items by ratio in descending order. 3. Start filling the knapsack until the weight limit.
from icecream import ic
def calculate_ratio(item):
name, weight, price = item
return price / weight
def fill_knapsack(items, capacity):
# Sort desc by ratio
sorted_items = sorted(items, key=calculate_ratio, reverse=True)
ic(sorted_items)
# Fill the knapsack until limit is reached
sack_items = []
total_weight = 0
total_price = 0
for item in sorted_items:
n, w, p = item
if total_weight + w <= capacity:
sack_items.append((n, w, calculate_ratio(item)))
total_weight += w
total_price += p
else:
fraction = (capacity - total_weight) / w
sack_items.append((n, int(fraction * w), calculate_ratio(item)))
total_weight += fraction * w
total_price += fraction * p
break
return total_price, total_weight, sack_items
# Items list
items = [
('A', 8, 40),
('B', 5, 30),
('C', 3, 20),
('D', 2, 15)]
# Knapsack capacity
capacity = 12
total_price, total_weight, sack_items = fill_knapsack(items, capacity)
ic(total_price, total_weight, sack_items);
"""
ic| sorted_items: [('D', 2, 15), ('C', 3, 20), ('B', 5, 30), ('A', 8, 40)]
ic| total_price: 75.0
total_weight: 12.0
sack_items: [('D', 2, 7.5), ('C', 3, 6.66), ('B', 5, 6.0), ('A', 2, 5.0)]
"""
Last update: 489 days ago
