Алгоритм, чтобы получить лучшую комбинацию

Question

Алгоритм, чтобы получить лучшую комбинацию

У меня есть предметы с идентификатором 1, 3, 4, 5, 6, 7, Теперь у меня есть данные, как следующие.
Для каждой строки есть предложение. Array of Ids состоят из комбинации ID в массиве. Discount это значение для этого offerId

offerId : Array of Ids     : Discount
o1      : [1]              : 45
o2      : [1 3 4]          : 100
o3      : [3 5]            : 55
o4      : [5]              : 40
o5      : [6]              : 30
o6      : [6 7]            : 20

Теперь я должен выбрать все предложения, которые дают мне наилучшую комбинацию идентификаторов, то есть максимальную общую скидку.

Например, в приведенном выше случае: возможные результаты могут быть:

[o2, o4, o5] максимальная скидка 170(100 + 40 + 30),

Заметка. результат offerId должен быть таким, чтобы идентификаторы не повторялись. Пример для o2,o4,o6 идентификаторы [1,3,4], [5], [6] все различны.

Другая комбинация может быть:
o1, o3, 06 для которых идентификаторы [1], [3,5], [6,7] Однако общее количество составляет 120 (45 + 55 + 20), что меньше, чем 170 как в предыдущем случае.

Мне нужен алгоритм / код, который поможет мне определить combination of offerIds который даст maximum discount учитывая, что каждое предложение должно содержать Ids,

НОТА Я пишу свой код в go язык. Но решения / логика на любом языке будут полезны.

НОТА : Я надеюсь, что смогу правильно объяснить свои требования. пожалуйста, прокомментируйте, если требуется дополнительная информация. Благодарю.

0

algorithm c++go

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

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

Пусть наши предложения будут структурами с полями offerNumber, setOfItems а также discount,
В целях реализации мы сначала нумеруем возможные элементы целыми числами от нуля до количества различных возможных элементов (скажем, k) минус один.
После этого мы можем представить setOfItems двоичным числом длины k,
Например, если k = 6 и setOfItems = 101110₂, этот набор включает в себя элементы 5, 3, 2 и 1 и исключает элементы 4 и 0, поскольку биты 5, 3, 2 и 1 равны единице, а биты 4 и 0 равны нулю.

Теперь позвольте f[s] быть лучшей скидкой, которую мы можем получить, используя точно установленный s предметов.
Вот, s может быть любым целым числом от 0 до 2^К — 1, представляющий один из 2^К возможные подмножества.
Кроме того, пусть p[s] быть в списке предложений, которые вместе позволяют нам получить скидку f[s] за набор предметов s,
Алгоритм работает следующим образом.

initialize f[0] to zero, p[0] to empty list
initialize f[>0] to minus infinity
initialize bestF to 0, bestP to empty list
for each s from 0 to 2^k - 1:
for each o in offers:
if s & o.setOfItems == o.setOfItems:  // o.setOfItems is a subset of s
if f[s] < f[s - o.setOfItems] + o.discount:  // minus is set subtraction
f[s] = f[s - o.setOfItems] + o.discount
p[s] = p[s - o.setOfItems] append o.offerNumber
if bestF < f[s]:
bestF = f[s]
bestP = p[s]

После этого, bestF это лучшая возможная скидка, и bestP это список предложений, которые дают нам эту скидку.

Сложность O (| предлагает | * 2^К) где k общее количество предметов.

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

initialize f[0] to zero, p[0] to empty list
initialize f[>0] to -1
initialize bestF to 0, bestP to empty list
for each s from 0 to 2^k - 1:
if f[s] >= 0:  // only for reachable s
if bestF < f[s]:
bestF = f[s]
bestP = p[s]
for each o in offers:
if s & o.setOfItems == 0:  // s and o.setOfItems don't intersect
if f[s + o.setOfItems] < f[s] + o.discount:  // plus is set addition
f[s + o.setOfItems] = f[s] + o.discount
p[s + o.setOfItems] = p[s] append o.offerNumber

2