Динамическое программирование для задачи о рюкзаке/Задачи/Копейка рубль бережет/Fadeev Vladimir

Материал из DISCOPAL
Перейти к: навигация, поиск

Для простоты вычислений предположим, что стоимость товара - копейки. То есть ничего в рублях нет. Это никак не повлияет на исходную задачу, так как в конце алгоритма мы получим список товаров, на которые мы должны сделать конкретную скидку в копейках.


Алгоритм:

1) Создаем словарь, где ключ - стоимость товара в копейках. И каждому ключу соответствует три значения - это имя товара, его количество и расчёт.

2) Проходим по всем товарам и записываем в наш словарь, все имена товаров и их количество под соответствующим ключом.

3) Для каждого ключа находим его расчёт( ("ключ" * "количество товара") % 100 ). И все эти значения суммируем.

4) Если эта сумма меньше 100, то эта та необходимая скидка, которую мы должны предоставить. То есть равномерно снижаем цену всем товарам.

4,1) Если же сумма больше 100, то находим остаток от деления на 100. Результат - необходимая скидка. И эту скидку стараемся предоставить равномерно самым дорогим товарам в копейках.


Рассмотрим пример, буквы - это название товара, числа - цена в копейках, порядок - то как они поступают на кассу (их сумма 530, значит в конце скидка должны быть 30 копеек)):

А: 50

Б: 40

В: 90

Г: 10

Д: 70

Е: 80

А: 50

В: 90

Ж: 50


Алгоритм:

1) Заводим словарь.


2) После выполнения второго пункта получим:

10: Г 1

40: Б 1

50: А 2, Ж 1

70: Д 1

80: Е 1

90: В 2


3) Находим расчёт:

10: 10 (10*1%100)

40: 40 (40*1%100)

50: 50 (50*3%100)

70: 70 (70*1%100)

80: 80 (80*1%100)

90: 80 (90*2%100)

Сумма = 330


4) Эта сумма больше 100, поэтому остаток от деления на 100 - это 30 (скидку, которую мы должны предоставить самым дорогим товарам).

Самый дорогой товар - "В" и их количество - 2.

Получается, что цена товара В снижена на 30/2 = 15 копеек. Это и есть наша скидка. И в итоге стоимость товара "В" - 75 копеек.


StasFomin (обсуждение) 11:43, 1 декабря 2016 (UTC): Это не сработает.

  • Представляйте товарную корзину правильно, для каждой строчки, — тип товара, его цена, число товаров.
  • Вы считаете, что всегда возможно дать скидку на «некратное ста» число копеек, поэтому предлагаете простой алгоритм «сдачу разбросать на какие-нибудь (какая разница — дорогие или нет) товары».
    • Это не всегда возможно. Допустим у вас 97 штук по 97 копеек — вы не сможете раскидать «09 копеек по 97 штукам»
    • Думайте о динамическом программировании. Тут не пройдут жадные эвристики.