Python knapsack program

Question

I have this data for the knapsack problem:

• List of product prices = MENU
• Most popular product count = MOST_POPULAR_COCKTAIL
• Knapsack price = CASH
• Knapsack length = CHECK_LEN

I need get all knapsack combinations from a list of products prices which satisfy:

• List of product prices bigger or equal knapsack length
• Each price in combination must multiply on different natural number in range from 1 to most popular product price
• Total combination price must equal knapsack price
• Combination length must equal knapsack length

settings.py

CASH = 6600 CHECK_LEN = 10 MOST_POPULAR_COCKTAIL = 12 MENU = [ {'Безалкогольные': [ { 'name': 'Мохито класический', 'buy_price': 40, 'sell_price': 150, 'sold_today': True, }, { 'name': 'Мохито клубничный', 'buy_price': 40, 'sell_price': 180, 'sold_today': True, }, { 'name': 'Мохито с сиропом', 'buy_price': 40, 'sell_price': 180, 'sold_today': True, }, ]}, {'Тропические': [ { 'name': 'Пляжный витамин', 'buy_price': 40, 'sell_price': 230, 'sold_today': True, }, { 'name': 'Пеликан', 'buy_price': 40, 'sell_price': 180, 'sold_today': True, }, { 'name': 'Наслаждение киви', 'buy_price': 40, 'sell_price': 200, 'sold_today': True, }, { 'name': 'Имбирный лимонад', 'buy_price': 40, 'sell_price': 150, 'sold_today': True, }, ]}, {'Молочные': [ { 'name': 'Молочный шейк', 'buy_price': 40, 'sell_price': 160, 'sold_today': True, }, ]}, {'Освежающие напитки': [ { 'name': 'Свежевыжатый сок', 'buy_price': 40, 'sell_price': 120, 'sold_today': True, }, { 'name': 'Лимонад', 'buy_price': 40, 'sell_price': 120, 'sold_today': True, }, ]}, {'Алкогольные': [ { 'name': 'Мохито классический', 'buy_price': 40, 'sell_price': 250, 'sold_today': True, }, { 'name': 'Мохито клубничный', 'buy_price': 40, 'sell_price': 250, 'sold_today': True, }, { 'name': 'Пина колада', 'buy_price': 40, 'sell_price': 280, 'sold_today': True, }, { 'name': 'Лонг айленд айс ти', 'buy_price': 40, 'sell_price': 350, 'sold_today': True, }, { 'name': 'Восход солнца', 'buy_price': 40, 'sell_price': 280, 'sold_today': True, }, { 'name': 'Секс на пляже', 'buy_price': 40, 'sell_price': 280, 'sold_today': True, }, { 'name': 'Дайкири клубничный', 'buy_price': 40, 'sell_price': 250, 'sold_today': True, }, { 'name': 'Голубая лагуна', 'buy_price': 40, 'sell_price': 250, 'sold_today': True, }, { 'name': 'Маргарита клубничная', 'buy_price': 40, 'sell_price': 250, 'sold_today': True, }, { 'name': 'Виски/ром кола', 'buy_price': 40, 'sell_price': 280, 'sold_today': True, }, ]}, {'Фьюжн': [ { 'name': 'Плантаторский пунш', 'buy_price': 40, 'sell_price': 250, 'sold_today': True, }, { 'name': 'Ураган', 'buy_price': 40, 'sell_price': 320, 'sold_today': True, }, { 'name': 'Май-тай', 'buy_price': 40, 'sell_price': 320, 'sold_today': True, }, { 'name': 'Джин физ клубничный', 'buy_price': 40, 'sell_price': 280, 'sold_today': True, }, { 'name': 'Московский мул', 'buy_price': 40, 'sell_price': 250, 'sold_today': True, }, ]}, ] 

knapsack.py

from itertools import product, izip from decorators import timer import settings class Product(object): def __init__(self, group, name, buy_price, sell_price, count=0): self.group = group self.name = name self.buy_price = buy_price self.sell_price = sell_price self.count = count self.price = count * sell_price self.profit = count * (sell_price - buy_price) class Check(object): def __init__(self, cash, length, most_popular_count, products): self.cash = cash self.length = length self.most_popular = most_popular_count self.products = products self.checks = [] def create_check(self, products_count): check = [] for i, count in enumerate(products_count): check.append(Product( self.products[i].group, self.products[i].name, self.products[i].buy_price, self.products[i].sell_price, count )) return check def remove_zeros(self, check): return tuple(product for product in check if product) def total_value(self, products_count): check = sum(n * product.sell_price for n, product in izip(products_count, self.products)) if check == self.cash and len(self.remove_zeros(products_count)) == self.length: tmp = self.create_check(products_count) self.print_check(tmp) self.checks.append(tmp) return check else: return -1 def knapsack(self): max_1 = [self.most_popular for p in self.products] max(product(*[xrange(n + 1) for n in max_1]), key=self.total_value) def print_check(self, check): def check_str(value, i): value = str(value) len_value = len(value.decode('utf-8')) if len_value < lengths[i]: value += ' ' * (lengths[i] - len_value) return value def print_header(): output_header = [] for i, name in enumerate(header): output_header.append(check_str(name, i)) print ' | '.join(output_header) def print_products(): for cocktail in check: if cocktail.count > 0: print ' | '.join([ check_str(cocktail.name, 0), check_str(cocktail.buy, 1), check_str(cocktail.sell, 2), check_str(cocktail.count, 3), check_str(cocktail.price, 4), check_str(cocktail.profit, 5) ]) header = ('Наименование', 'Покупка', 'Продажа', 'Кол-во', 'Сумма', 'Прибыль') lengths = [len(name.decode('utf-8')) for name in header] spend_sum = 0 count = 0 for cocktail in check: spend_sum += cocktail.price count += cocktail.count lengths[0] = max(lengths[0], len(cocktail.name.decode('utf-8'))) lengths[1] = max(lengths[1], len(str(cocktail.buy_price))) lengths[2] = max(lengths[2], len(str(cocktail.sell_price))) lengths[3] = max(lengths[3], len(str(cocktail.count))) lengths[4] = max(lengths[4], len(str(cocktail.price))) lengths[5] = max(lengths[5], len(str(cocktail.profit))) print_header() print '-' * (sum(lengths) + 15) print_products() print '-' * (sum(lengths) + 15) print 'Закупка: %d руб.' % spend_sum print 'Продажи: %d шт. на %d руб.' % (count, self.cash) print 'Прибыль: %d руб.' % (self.cash - spend_sum) def main(): products = [] for group in settings.MENU: key = group.keys()[0] for cocktail in group[key]: if cocktail['sold_today']: products.append(Product(key, cocktail['name'], cocktail['buy_price'], cocktail['sell_price'])) check = Check(settings.CASH, settings.CHECK_LEN, settings.MOST_POPULAR_COCKTAIL, products) check.knapsack() main() 

With that algorithm I'll die faster than program solve problem. Could anybody help make this faster?

Answer 1

I'll die faster than program solve problem

I certainly hope you haven't died, though perhaps your program has been running for the eleven years since you posted this.

Performance aside, the code would never have worked, for the following reasons:

• Your usage of max() is incorrect. The return value is discarded, and the only reason the code does anything is that self.total_value has a surprise side-effect and mutates the class instance.
• cocktail.buy and cocktail.sell are undefined; these should have been cocktail.buy_price and cocktail.sell_price.

This program was written for Python 2. When this question was posted (2013), Python 2 had not yet been deprecated, but Python 3.3 already had a stable release. The remainder of my feedback will assume a migration to Python 3, because Python 2 has now been fully deprecated for four years. In your code, this requires:

• Replacing statement print x with function-call print(x)
• Removing your calls to decode()
• Replacing izip and xrange with zip and range

Your decorators.timer was unused, so remove it.

MOST_POPULAR_COCKTAIL is an extreme misnomer. Functionally, this is actually something like MAX_QUANTITY_PER_PRODUCT.

Arguably, "bill" may be clearer than "check" in context as "check" has more alternative meanings that may be confusing in software development. (English is hard.)

Your MENU is not well-designed structurally. Rather than it being a list of dictionaries of lists of dictionaries, it should only be a dictionary of lists of dictionaries (i.e. the outer level should have categories as its keys). If you were to keep this structure, you should also prefer tuples over lists for immutability. Even better, reduce to a dictionary of dictionaries where the inner key is the product name.

It's somewhat strange in a backpack-like problem to require that the cash exactly equal the total bill (the dot product of quantities and sale prices). I would typically expect that it makes more business sense to require that the total bill be at most the cash reserve. Since total_value returns the total bill, and the total bill had been constrained to equal CASH, this isn't even convex optimization anymore; it's non-objective constraint optimization and the first arbitrary solution that meets this criterion would be taken. Let's assume that that isn't what you want, and that instead: if there are no solutions for which the total bill exactly equals the cash reserve, then you still want the best solution. "Best" now requires reinterpretation. From the perspective of the customer, "best" may mean the most products purchased. From the vendor perspective, "best" may mean most profit. Since you bother to output profit in your final table, let's assume that we optimize from a vendor perspective and maximize vendor profit for some CASH constraint at the purchasing side. A realistic scenario would be a party planner working for the tavern that is given a purchase budget by the customer.

Another surprising constraint in the original code is that the number of selected product types must strictly equal some given CHECK_LEN. The less-surprising constraint would be that the number of selected product types must be at mostBILL_LEN to limit some per-product-type administrative cost. However, we may imagine that this is deliberate to promote "purchase order diversity", so let's keep this one, perhaps with a clearer name.

All of this amounts to a modified backpack problem that can be expressed in a straightforward manner with linear programming. It executes quite quickly.

import locale import pandas as pd import pulp def make_vars( menu: dict[str, dict[str, dict[str, int | bool]]], max_quantity_per_product: int, ) -> pd.DataFrame: df = pd.DataFrame([ {'category': cat_name, 'name': name} | props for cat_name, cat in menu.items() for name, props in cat.items() ]) # Drop menu items that were not sold today df = df[df['sold_today']] df['product_name'] = df['category'] + ' ' + df['name'] df['unit_profit'] = df['sell_price'] - df['buy_price'] df['assign'] = pulp.LpVariable.matrix( name='assign', cat=pulp.LpBinary, indices=df['product_name'], ) df['quantity'] = pulp.LpVariable.matrix( name='quantity', cat=pulp.LpInteger, indices=df['product_name'], lowBound=0, upBound=max_quantity_per_product, ) df['profit'] = df['unit_profit'] * df['quantity'] return df def make_problem(df: pd.DataFrame) -> tuple[ pulp.LpProblem, pulp.LpAffineExpression, ]: prob = pulp.LpProblem(name='tavern_backpack', sense=pulp.LpMaximize) profit = pulp.lpSum(df['profit']) prob.setObjective(profit) return prob, profit def add_constraints( prob: pulp.LpProblem, df: pd.DataFrame, bill_len: int, cash: float, ) -> pulp.LpAffineExpression: prob.addConstraint( name='order_diversity', constraint=pulp.lpSum(df['assign']) == bill_len, ) sales = pulp.lpDot(df['sell_price'], df['quantity']) prob.addConstraint(name='cash', constraint=sales <= cash) # Associate binary assignment with quantity per row # assign == 1 IIF quantity > 0 for i, row in df.iterrows(): prob.addConstraint( name='qty_hi_' + row['product_name'], constraint=row['assign'] <= row['quantity'], ) return sales def solve(prob: pulp.LpProblem, df: pd.DataFrame) -> None: prob.solve() if prob.status != pulp.LpStatusOptimal: raise ValueError(prob.status) affine_cols = ['assign', 'quantity', 'profit'] df[affine_cols] = df[affine_cols].map(pulp.value) def display( df: pd.DataFrame, profit: pulp.LpAffineExpression, sales: pulp.LpAffineExpression, ) -> None: locale.setlocale(category=locale.LC_ALL, locale='ru_RU.UTF-8') disp = df.loc[ df['assign'] > 0.5, ['category', 'name', 'buy_price', 'sell_price', 'unit_profit', 'quantity', 'profit'], ] disp['quantity'] = disp['quantity'].astype(int) money_cols = ['buy_price', 'sell_price', 'unit_profit', 'profit'] disp[money_cols] = disp[money_cols].map(locale.currency, grouping=True) pd.options.display.max_columns = 20 pd.options.display.width = 300 print(disp) print('Purchase:', locale.currency(df['quantity'].dot(df['buy_price']))) print( 'Sales:', disp['quantity'].sum(), 'pieces for', locale.currency(sales.value(), grouping=True), ) print('Profit:', locale.currency(profit.value(), grouping=True)) def main() -> None: menu = { 'Non-alcoholic': { 'Classic Mojito': {'buy_price': 40, 'sell_price': 150, 'sold_today': True}, 'Strawberry Mojito': {'buy_price': 40, 'sell_price': 180, 'sold_today': True}, 'Mojito with syrup': {'buy_price': 40, 'sell_price': 180, 'sold_today': True}, }, 'Tropical': { 'Beach Vitamin': {'buy_price': 40, 'sell_price': 230, 'sold_today': True}, 'Pelican': {'buy_price': 40, 'sell_price': 180, 'sold_today': True}, 'Kiwi Delight': {'buy_price': 40, 'sell_price': 200, 'sold_today': True}, 'Ginger Lemonade': {'buy_price': 40, 'sell_price': 150, 'sold_today': True}, }, 'Dairy': { 'Milkshake': {'buy_price': 40, 'sell_price': 160, 'sold_today': True}, }, 'Refreshments': { 'Freshly squeezed juice': {'buy_price': 40, 'sell_price': 120, 'sold_today': True}, 'Lemonade': {'buy_price': 40, 'sell_price': 120, 'sold_today': True}, }, 'Alcohol': { 'Mojito classic': {'buy_price': 40, 'sell_price': 250, 'sold_today': True}, 'Strawberry Mojito': {'buy_price': 40, 'sell_price': 250, 'sold_today': True}, 'Pina Colada': {'buy_price': 40, 'sell_price': 280, 'sold_today': True}, 'Long Island Ice Tea': {'buy_price': 40, 'sell_price': 350, 'sold_today': True}, 'Sunrise': {'buy_price': 40, 'sell_price': 280, 'sold_today': True}, 'Sex on the beach': {'buy_price': 40, 'sell_price': 280, 'sold_today': True}, 'Strawberry Daiquiri': {'buy_price': 40, 'sell_price': 250, 'sold_today': True}, 'Blue Lagoon': {'buy_price': 40, 'sell_price': 250, 'sold_today': True}, 'Strawberry margarita': {'buy_price': 40, 'sell_price': 250, 'sold_today': True}, 'Whiskey/rum cola': {'buy_price': 40, 'sell_price': 280, 'sold_today': True}, }, 'Fusion': { 'Plantation Punch': {'buy_price': 40, 'sell_price': 250, 'sold_today': True}, 'Hurricane': {'buy_price': 40, 'sell_price': 320, 'sold_today': True}, 'Mai Tai': {'buy_price': 40, 'sell_price': 320, 'sold_today': True}, 'Strawberry Fizz Gin': {'buy_price': 40, 'sell_price': 280, 'sold_today': True}, 'Moscow Mule': {'buy_price': 40, 'sell_price': 250, 'sold_today': True}, }, } df = make_vars(menu=menu, max_quantity_per_product=12) prob, profit = make_problem(df=df) sales = add_constraints(prob=prob, df=df, bill_len=10, cash=6_600) solve(prob=prob, df=df) display(df=df, profit=profit, sales=sales) if __name__ == '__main__': main() 

... Result - Optimal solution found Objective value: 5760.00000000 Enumerated nodes: 0 Total iterations: 3 Time (CPU seconds): 0.01 Time (Wallclock seconds): 0.01 Option for printingOptions changed from normal to all Total time (CPU seconds): 0.01 (Wallclock seconds): 0.01 category name buy_price sell_price unit_profit quantity profit 2 Non-alcoholic Mojito with syrup 40,00 ₽ 180,00 ₽ 140,00 ₽ 1 140,00 ₽ 12 Alcohol Pina Colada 40,00 ₽ 280,00 ₽ 240,00 ₽ 1 240,00 ₽ 13 Alcohol Long Island Ice Tea 40,00 ₽ 350,00 ₽ 310,00 ₽ 12 3 720,00 ₽ 14 Alcohol Sunrise 40,00 ₽ 280,00 ₽ 240,00 ₽ 1 240,00 ₽ 15 Alcohol Sex on the beach 40,00 ₽ 280,00 ₽ 240,00 ₽ 1 240,00 ₽ 19 Alcohol Whiskey/rum cola 40,00 ₽ 280,00 ₽ 240,00 ₽ 1 240,00 ₽ 20 Fusion Plantation Punch 40,00 ₽ 250,00 ₽ 210,00 ₽ 1 210,00 ₽ 21 Fusion Hurricane 40,00 ₽ 320,00 ₽ 280,00 ₽ 1 280,00 ₽ 23 Fusion Strawberry Fizz Gin 40,00 ₽ 280,00 ₽ 240,00 ₽ 1 240,00 ₽ 24 Fusion Moscow Mule 40,00 ₽ 250,00 ₽ 210,00 ₽ 1 210,00 ₽ Purchase: 840,00 ₽ Sales: 21 pieces for 6 600,00 ₽ Profit: 5 760,00 ₽