есть магазин.
если покупаешь от 1 товар платишь 10 рублей за штуку
от 3 товаров платишь 25 рублей за 3 штуки,
от 5 товаров платишь 40 рублей за 5 штук
от 100 товаров платишь 70 рублей
нужен алгоритм коорый будет оптимальную сумму давать.
к примеру для 8 чтобы давал 5+ 3, а не от 100
Здравствуйте, merge, Вы писали:
M>нужен алгоритм коорый будет оптимальную сумму давать.
Задача простая, в чем сложность?
Приобретаешь всегда максимально возможную партию.
Это работает, если по мере увеличения партии цена за одну штуку снижается (так обычно и бывает).
Здравствуйте, Буравчик, Вы писали:
Б>Здравствуйте, merge, Вы писали:
M>>нужен алгоритм коорый будет оптимальную сумму давать.
Б>Задача простая, в чем сложность? Б>Приобретаешь всегда максимально возможную партию. Б>Это работает, если по мере увеличения партии цена за одну штуку снижается (так обычно и бывает).
в моем кейсе если покупаю 8 штук надо вернуть 65, как 5+ 3, а не 70
Здравствуйте, gandjustas, Вы писали:
G>Здравствуйте, merge, Вы писали:
M>>в моем кейсе если покупаю 8 штук надо вернуть 65, как 5+ 3, а не 70
G>Задача о рюкзаке. В общем случае перебор.
В этом конкретном случае, полный пребор O(N*M) (N-число штук для покупки, M-число позиций в прайслите), так что не рюкзак.
def optimize( n : int, prices : dict, precalc : dict = {} ):
if n<=0 :
return []
if n in precalc :
return precalc.get(n)
def calc_price(by_list: list):
return sum(prices.get(k) for k in by_list)
ceses = [ [k]+optimize(n-k, prices, precalc) for k in prices.keys() ]
result = min( ceses, key = calc_price)
precalc[n]=result
return result
Здравствуйте, Chorkov, Вы писали: C>В этом конкретном случае, полный пребор O(N*M) (N-число штук для покупки, M-число позиций в прайслите), так что не рюкзак. C>
Скрытый текст
C>def optimize( n : int, prices : dict, precalc : dict = {} ):
C> if n<=0 :
C> return []
C> if n in precalc :
C> return precalc.get(n)
C> def calc_price(by_list: list):
C> return sum(prices.get(k) for k in by_list)
C> ceses = [ [k]+optimize(n-k, prices, precalc) for k in prices.keys() ]
C> result = min( ceses, key = calc_price)
C> precalc[n]=result
C> return result
C>
была возможность купить 9 предметов за 64 рубля. Такая цена не противоречит схеме ценообразования "оптом — дешевле", но не найдётся таким наивным алгоритмом.
Здравствуйте, Chorkov, Вы писали:
G>>Задача о рюкзаке. В общем случае перебор. C>В этом конкретном случае, полный пребор O(N*M) (N-число штук для покупки, M-число позиций в прайслите), так что не рюкзак.
Как я понял, тут может быть ситуация что если тебе нужно 98штук, то купить коробку 100шт и две выкинуть может оказаться дешевле, чем набирать ровно 98 из более мелких коробок.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Здравствуйте, ·, Вы писали:
·>Здравствуйте, Chorkov, Вы писали:
G>>>Задача о рюкзаке. В общем случае перебор. C>>В этом конкретном случае, полный пребор O(N*M) (N-число штук для покупки, M-число позиций в прайслите), так что не рюкзак. ·>Как я понял, тут может быть ситуация что если тебе нужно 98штук, то купить коробку 100шт и две выкинуть может оказаться дешевле, чем набирать ровно 98 из более мелких коробок.
Здравствуйте, watchmaker, Вы писали:
W>Здравствуйте, Chorkov, Вы писали:
C>
W>И, кстати говоря, иногда всё же выгоднее купить больше, а потом выбросить лишнее. Например, если бы среди исходных вариантов
была возможность купить 9 предметов за 64 рубля. Такая цена не противоречит схеме ценообразования "оптом — дешевле", но не найдётся таким наивным алгоритмом.
тут идея именно в алгоритме, а не в том, что выгоднее и могло быть 9 предметов за 64
Здравствуйте, Chorkov, Вы писали:
C>Здравствуйте, gandjustas, Вы писали:
G>>Здравствуйте, merge, Вы писали:
M>>>в моем кейсе если покупаю 8 штук надо вернуть 65, как 5+ 3, а не 70
G>>Задача о рюкзаке. В общем случае перебор.
C>В этом конкретном случае, полный пребор O(N*M) (N-число штук для покупки, M-число позиций в прайслите), так что не рюкзак.
C>
C>def optimize( n : int, prices : dict, precalc : dict = {} ):
C> if n<=0 :
C> return []
C> if n in precalc :
C> return precalc.get(n)
C> def calc_price(by_list: list):
C> return sum(prices.get(k) for k in by_list)
C> ceses = [ [k]+optimize(n-k, prices, precalc) for k in prices.keys() ]
C> result = min( ceses, key = calc_price)
C> precalc[n]=result
C> return result
C>
Здравствуйте, merge, Вы писали:
M>есть магазин. M>если покупаешь от 1 товар платишь 10 рублей за штуку M>от 3 товаров платишь 25 рублей за 3 штуки, M>от 5 товаров платишь 40 рублей за 5 штук M>от 100 товаров платишь 70 рублей
M>нужен алгоритм коорый будет оптимальную сумму давать. M>к примеру для 8 чтобы давал 5+ 3, а не от 100
Если зависимость монотонная, то жадный алгоритм, это же очевидно. Если не монотонная, то это задача о рюкзаке и NP решения пока не существует.
M>вот этот момент не осилил. что тут? M>ceses = [ [k]+optimize(n-k, prices, precalc) for k in prices.keys() ]
Цикле по всем возможным ключам в прайслисте:
пробуем составитиь список из [k] ранее найденного решения для n-k.
ceses — список возможных решений для текущего n.
ceses = []
for k in prices.keys():
ceses+= [ [k] + optimize(n-k, prices, precalc) ]
например для n==5, ceses==[[1, 1, 5], [3, 1, 3], [5, 1, 1], [9], [100]]
