Здравствуйте.
Требуется решить задачу со следующими данными:
- Список продуктов с их стоимостью
- Объем наличности
- Кол-во позиций в чеке
- Максимальное кол-во продукта в наборе
По этим данным нужно найти ВСЕ наборы продуктов, которые удовлетворяют условиям:
- Любой продукт может быть положен в набор не более, указанного в условии, максимально кол-ва
- Стоимость набора должна равняться объему наличности
- Длина набора должна равняться кол-ву позиций в чеке
Я написал решение на Python'не, но это не вариант, решается бесконечно долго.
settings.pyCASH = 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.pyfrom 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()
Почитал, где разбирается похожая задача, решенная с использованием PuLP. Но составить задачу для PuLP не получается. Хотел бы получить помощь с нахождением хотя бы одного набора.
