Knapsack Overflow Problem

knapsack_overflow.py

"""
Solves the Knapsack overflow problem.

In this problem, we attempt to fill a Knapsack with items. 

The constraints:
- The Knapsack may not underflow (i.e. the Knapsack must have no space left)
- The Knapsack may overflow
- The value of items should be minimized
- The quantity should be minimized

Computational complexity: O(n)
"""
from copy import deepcopy
from typing import List, Dict
from collections import defaultdict


class Knapsack:
    def __init__(self, min_weight: int):
        self.min_weight = min_weight
        self.weight = 0
        self.items = []
        self.price = 0

    def add(self, item: dict):
        self.weight += item['quantity']
        self.price += item['price']
        self.items.append(item)

    def remove(self, item: dict):
        self.weight -= item['quantity']
        self.price -= item['price']
        self.items.remove(item)

    def fits(self, item: Dict[str, int]):
        return item['quantity'] <= self.min_weight - self.weight

    def __str__(self):
        items = defaultdict(int)
        for item in self.items:
            items[item['quantity']] += 1
        formatted_items = ["{} x {}".format(i, items[i]) for i in items]
        return "KnapSack(price={}, weight={}, items={})".format(
            self.price, self.weight, formatted_items
        )

    __repr__ = __str__


def best_price(items: List[Dict[str, int]]) -> Dict[str, int]:
    """
    Given a list of items, find the best price/quantity ratio.
    """
    best_ratio = None
    cheapest_item = None
    for item in items:
        ratio = item["price"] / item["quantity"]
        if best_ratio is None or best_ratio > ratio:
            best_ratio = ratio
            cheapest_item = item
    return cheapest_item


def find_solutions(knap_sack: Knapsack, items: List[Dict[str, int]]):
    """
    Find ways to fill the Knapsack, given the items.
    
    Algorithm:
    1. Find the item that has the best quantity/price ratio
    2. Check if it fits
        If it does, fill it.
            if exact match: stop
        If it doesn't fill it anyway and mark it as a solution.
            Remove item from Knapsack
            Remove item from availabile items
    3. Goto 1.
    solution := min(price), min(quantity)
    """ 
    solutions = []
    while knap_sack.weight < knap_sack.min_weight:
        item = best_price(items)
        if not item:
            print('items exhausted')
            break
        if not knap_sack.fits(item):
            knap_sack.add(item)
            solution = deepcopy(knap_sack)
            solutions.append(solution)

            knap_sack.remove(item)
            items.remove(item)
            continue

        knap_sack.add(item)
        if knap_sack.weight == knap_sack.min_weight:
            solution = deepcopy(knap_sack)
            solutions.append(solution)
    return solutions


desired_quantity = 3780  # grams
knapsack = Knapsack(desired_quantity)
items = [{"quantity": 60, "price": 4}, {"quantity": 100, "price": 6}, {"quantity": 200, "price": 10}]
solutions = find_solutions(knapsack, items)

# Minimalize price and then quantity. If there are solutions
# with the same price, choose the one with the lowest quantity
print(solutions)