Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- """
- 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)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement