edited tags

Link

edited Oct 4, 2024 at 20:03

Reinderien

71.1k
5
76
256

deleted 83 characters in body

Source Link

edited Feb 3, 2016 at 21:10

Jamal

35.2k
13
134
238

How to make python Python knapsack program faster

I have this data for the knapsack problem:

I have data:

List of product prices = MENUMENU
Most popluarpopular product count = MOST_POPULAR_COCKTAILMOST_POPULAR_COCKTAIL
Knapsack price = CASHCASH
Knapsack length = CHECK_LENCHECK_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 difrentdifferent natural number in range range from 1 to most popluarpopular product price
Total combination price must equal knapsack price
Combination length must equal knapsack length

I wrote program on Python, it contains two files.

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,
        },
    ]},
]

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,
        },
    ]},
]

and knapsack.py

With that algorithm I'll die faster than program solve problem.

Could anybody help make this faster.?

How to make python knapsack program faster

I have knapsack problem:

I have data:

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

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

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

I wrote program on Python, it contains two files.

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,
        },
    ]},
]

and knapsack.py

With that algorithm I'll die faster than program solve problem.

Could anybody help make this faster.

Python knapsack program

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

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

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

python performance algorithm combinatorics

Tweeted twitter.com/#!/StackCodeReview/status/625672993700741120

occurred Jul 27, 2015 at 14:24

Source Link

asked Jul 16, 2013 at 18:00

lmasikl

109
3

How to make python knapsack program faster

I have knapsack problem:

I have data:

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

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

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

I wrote program on Python, it contains two files.

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,
        },
    ]},
]

and 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.

python algorithm combinatorics

Stack Exchange Network

Return to Question

How to make python Python knapsack program faster

How to make python knapsack program faster

Python knapsack program

How to make python knapsack program faster