Solving the knapsack problem using PuLP?

Question

Python

Hello.
It is required to solve a problem with the following data:

• List of products with their prices
  
• Cash volume
  
• Number of positions in the receipt
  
• Maximum number of product in a set
  

Based on this data, you need to find ALL sets of products that satisfy the conditions:

• Any product can be put in a set no more than specified in the condition, the maximum number
  
• The cost of the set must equal the amount of cash
  
• The length of the set must be equal to the number of positions in the receipt
  

I wrote a solution in Python, but this is not an option, it takes forever to solve.
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

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 print_reports(self):
        print len(self.checks)


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()
    check.print_reports()

main()

I read where a similar problem is solved using PuLP. But it is not possible to create a task for PuLP. I would like to get help with finding at least one set.