CasperCL · September 30, 2019 07:32
diff --git a/knapsack_overflow.py b/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)
	"""
	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)