Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Решение задачио рюкзаке с применением PuLP

Anna | 16.06.2014 | нет комментариев
Здравствуйте.
Требуется решить задачу со следующими данными:

  • Список продуктов с их стоимостью
  • Объем наличности
  • Кол-во позиций в чеке
  • Наивысшее кол-во продукта в комплекте

По этим данным необходимо обнаружить ВСЕ комплекты продуктов, которые удовлетворяют условиям:

  • Всякий продукт может быть положен в комплект не больше, указанного в условии, максимально кол-ва
  • Стоимость комплекта должна равняться объему наличности
  • Длина комплекта должна равняться кол-ву позиций в чеке

Я написал решение на Python’не, но это не вариант, решается безгранично длинно.

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()

Почитал, где разбирается схожая задача, решенная с применением PuLP. Но составить задачу для PuLP не получается. Хотел бы получить поддержка с нахождением правда бы одного комплекта.

 

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB