Алгоритм поиска комбинации с самой низкой ценой

У меня есть набор продуктов (корзина для покупок) и набор скидок/предложений, которые будут применяться к продуктам из корзины пользователя, но также возможно, что продукт внутри корзины подходит более чем к одному предложению. Я пытаюсь найти алгоритм, который выбирает из набора продуктов, какие скидки/предложения применять и какие продукты. Например: корзина, состоящая из 5 товаров со следующими базовыми ценами:

p1: 6€
p2: 6€
p3: 9€
p4: 8€
p5: 12€

И следующие скидки/предложения:

(p1, p5):     18€ => 10€   (you save 8€, or a 44.44%)
(p1, p2):     12€ => 9€    (you save 3€, or a 25%)
(p2, p3, p4): 23€ => 21€   (you save 2€, or a 8.70%)
p3:           9€ => 8€   (you save 1€, or a 11.00%)

И, конечно же, если вы применяете предложение (p1, p5), вы не можете выбрать предложение (p1, p2), потому что тогда повторяется p1, или скидки (p3, p4, p5) и p3. Алгоритм, который я ищу, — это набор предложений, которые можно выбрать, чтобы сэкономить максимальную сумму денег, с ограничением, что ни один продукт не может получить более одной скидки/предложения.

Подход состоит в том, чтобы начать с предложения, которое обеспечивает наибольшую экономию, и выбрать в этом порядке предложения, которые не добавляют ни один продукт более одного раза:

(1) Choose (p1, p5): 10€
    Reject (p1, p2): p1 repeated
(2) Choose (p2, p3, p4): 21€
    Reject p3: repeated
    Reject p2: repeated
    Reject p4: repeated
End: we already have p1, p2, p3, p4 and p5
Total: 31€

Другой подход заключается в том, чтобы начать с предложения, которое экономит «пропорционально» (относительно совокупной базовой цены) больше денег:

(1) Choose (p1, p5): 10€
    Reject (p1, p2): p1 repeated
(2) Choose p3: 8€
    Reject (p2, p3, p4): p3 repeated
(3) Choose p2: 6€
(4) Choose p4: 8€
End: we already have p1, p2, p3, p4 and p5
Total: 32€

В данном конкретном случае побеждает «экономия большего количества денег», но у меня есть контрпримеры, когда побеждает «пропорциональная экономия». Я пробовал даже с «пропорциональной экономией» по отношению к базовой цене корзины.

Каков наилучший алгоритм в этом случае?

ПРИМЕЧАНИЕ. Предпочтительный язык для иллюстрации вашего решения, псевдокод или C++.

ПРИМЕЧАНИЕ. Связанная "повторяющаяся проблема" не имеет решения вопроса. Хотя формулировка сильно отличается (я еще не до конца понял связанный вопрос).


algorithm combinations minimization
person Peregring-lk    schedule 10.01.2017    source источник
comment
Вместо того, чтобы думать об этом как о максимизации сбережений, подумайте об этом как о минимизации затрат. Вы можете расширить предложения, чтобы у каждого предмета также было предложение из 1 предмета, которое ничего не экономит. Тогда проблема заключается в том, что у вас есть семейство подмножеств, объединение которых задано набором, и каждое из этих подмножеств имеет связанную стоимость, и ваша цель состоит в том, чтобы найти минимально стоящий раздел набора, где ячейки раздела взяты из наборов. Ее легко сформулировать как задачу целочисленного программирования и, следовательно, решить с помощью таких инструментов.   -  person John Coleman    schedule 10.01.2017
comment
@JohnColeman Проблема в размере набора возможных комбинаций. Должен существовать алгоритм для сортировки предложений и базовых цен таким образом, чтобы его можно было пройти линейно, как я пытался сделать (аналогично поиску минимального пути или нетерпеливым алгоритмам).   -  person Peregring-lk    schedule 10.01.2017
comment
Я думаю, что это может быть проблема семейства: en.wikipedia.org/wiki/Set_cover_problem   -  person Peregring-lk    schedule 10.01.2017
comment
Проблема почти наверняка является NP-трудной, хотя такого рода проблемы, как правило, имеют псевдополиномиальные решения, которые можно найти с помощью подходов динамического программирования.   -  person John Coleman    schedule 10.01.2017
comment
Кажется, что эту проблему можно рассматривать как проблему взвешенной упаковки множества: en.wikipedia.org/wiki/ Set_packing   -  person John Coleman    schedule 10.01.2017