3
\$\begingroup\$

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?

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.