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
    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)]
"""