Информация об изменениях

Сообщение Re[5]: Оптимизация расходов от 22.03.2021 18:28

Изменено 23.03.2021 10:03 watchmaker

Старый текст
Новый текст
Разница

Re[5]: Оптимизация расходов

Здравствуйте, 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>

Конечно это настолько не рюкзак, что у тебя при этом написана вариация на классический псевдополиномиальный алгоритм для рюкзака https://en.wikipedia.org/wiki/Pseudo-polynomial_time#Knapsack_problem

И, кстати говоря, иногда всё же выгоднее купить больше, а потом выбросить лишнее. Например, если бы среди исходных вариантов была возможность купить 9 предметов за 64 рубля. Такая цена не противоречит схеме ценообразования "оптом — дешевле", но не найдётся таким наивным алгоритмом.

Re[5]: Оптимизация расходов

Скрытый текст

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 рубля. Такая цена не противоречит схеме ценообразования "оптом — дешевле"~~, но не найдётся таким наивным алгоритмом~~.