# minte9 LearnRemember

### 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

# 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: 19 days ago