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

Question

Вот моя проблема. Представьте, что я покупаю 3 разных товара, и у меня есть до 5 купонов. Купоны являются взаимозаменяемыми, но стоят разную сумму при использовании на разных предметах.

Вот матрица, которая дает результат расходования разного количества купонов на разные товары:

coupons:    1         2         3         4         5
item 1      $10 off   $15 off
item 2                $5 off    $15 off   $25 off   $35 off
item 3      $2 off

Я вручную разработал лучшие действия для этого примера:

• Если у меня есть 1 купон, пункт 1 получает его за 10 долларов
• Если у меня есть 2 купона, пункт 1 получает их за 15 долларов
• Если у меня есть 3 купона, предмет 1 получает 2, а предмет 3 получает 1, при скидке 17 долларов
• Если у меня есть 4 купона, то либо :
  • Предмет 1 получает 1, а предмет 2 получает 3 на общую сумму 25 долларов США или
  • Пункт 2 получает все 4 за 25 долларов.
• Если у меня есть 5 купонов, то пункт 2 получает все 5 за 35 долларов.

Однако мне нужно разработать общий алгоритм, который будет обрабатывать разные матрицы и любое количество предметов и купонов.

Я подозреваю, что мне нужно будет пройтись по каждой возможной комбинации, чтобы найти лучшую цену для n купонов. У кого-нибудь есть идеи?

Answer 1

Это хороший кандидат для динамического программирования:

//int[,] discountTable = new int[NumItems][NumCoupons+1]

// bestDiscount[i][c] means the best discount if you can spend c coupons on items 0..i
int[,] bestDiscount = new int[NumItems][NumCoupons+1];

// the best discount for a set of one item is just use the all of the coupons on it
for (int c=1; c<=MaxNumCoupons; c++)
    bestDiscount[0, c] = discountTable[0, c];

// the best discount for [i, c] is spending x coupons on items 0..i-1, and c-x coupons on item i
for (int i=1; i<NumItems; i++)
    for (int c=1; c<=NumCoupons; c++)
        for (int x=0; x<c; x++)
            bestDiscount[i, c] = Math.Max(bestDiscount[i, c], bestDiscount[i-1, x] + discountTable[i, c-x]);

В конце этого лучшей скидкой будет наибольшее значение bestDiscount [NumItems] [x]. Чтобы восстановить дерево, следуйте графику в обратном направлении:

изменить, чтобы добавить алгоритм:

//int couponsLeft;

for (int i=NumItems-1; i>=0; i++)
{
    int bestSpend = 0;
    for (int c=1; c<=couponsLeft; c++)
        if (bestDiscount[i, couponsLeft - c] > bestDiscount[i, couponsLeft - bestSpend])
            bestSpend = c;

    if (i == NumItems - 1)
        Console.WriteLine("Had {0} coupons left over", bestSpend);
    else
        Console.WriteLine("Spent {0} coupons on item {1}", bestSpend, i+1);

    couponsLeft -= bestSpend;
}
Console.WriteLine("Spent {0} coupons on item 0", couponsLeft);

Сохранение графика в вашей структуре данных - это тоже хороший способ, но я так и думал.

Answer 2

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

Answer 3

Я думаю, динамическое программирование должно сделать это. По сути, вы отслеживаете массив A [n, c], значения которого означают оптимальную скидку при покупке n первых товаров, потративших c купонов. Значения a [n, 0] должны быть 0 для всех значений n, так что это хорошее начало. Кроме того, A [0, c] равно 0 для всех c.

Когда вы оцениваете A [n, c], вы перебираете все предложения скидок для элемента n и добавляете скидку для этого конкретного предложения к A [n-1, cp], где p - цена в купонах для этого конкретного скидка. [N-1, c-p], конечно, должен быть рассчитан (таким же образом) до этого. Сохраняйте лучшие комбинации и сохраняйте их в массиве.

Рекурсивная реализация, вероятно, дала бы самую чистую реализацию. В этом случае вы должны найти ответ в A [N, C], где N - общее количество товаров, а C - общее количество доступных купонов.

Answer 4

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

Для вашего примера:

Пусть 0 <= xi <= 1 </em>

• x1 = Один, если на 1-й элемент потрачен один купон, в противном случае - ноль
• x2 = Один, если на 1 пункт потрачено два купона, в противном случае - ноль
• x3 = Один, если на купон 2 потрачен один купон, в противном случае - ноль
• x4 = Один, если на купон 2 потрачены два купона, в противном случае ноль
• x5 = Один, если на купон 3 потрачено три купона, в противном случае ноль
• ...

Предположим, что если я потрачу два купона на предмет 1, то оба x1 и x2 равны одному. Это подразумевает ограничение

• x1> = x2

С аналогичными ограничениями для других предметов, например,

• x3> = x4
• x4> = x5

сэкономленная сумма

• Сохранено = 10 x1 + 5 x2 + 0 x3 + 5 x4 + 10 x5 + ...

Если вы хотите найти наибольшее количество сэкономленных денег с фиксированным числом купонов, то вы хотите минимизировать Сохранено с учетом вышеуказанных ограничений и дополнительного ограничения:

• количество купонов = x1 + x2 + x3 + ...

Это работает для любой матрицы и количества предметов. Меняя нотацию (и мне грустно, что я не могу подписаться), пусть 0 <= y_ij <= 1 </em> будет единица, если на номер элемента i * потрачено j купонов 1078 *. У нас есть ограничения

• y_i (j-1)> = y_ij

Если сумма, сэкономленная на расходах j , купонов на элемент i равна M_ij , где мы определяем M_i0 = 0 , то максимизировать

• Сохранено = Sum_ij (M_ij - M_i (j-1)) y_ij

с учетом вышеуказанных ограничений и

• количество купонов = Sum_ij y_ij

(форматирование курсивом здесь не работает)

Answer 5

Я подозреваю, что какой-то сортированный список для запоминания каждого купона может помочь здесь.

например, если у вас есть 4 купона, оптимально возможно:

1. используя все 4 на чем-то. Вы должны проверить все эти новые цены.
2. с использованием 3 и 1. Либо 3-элемент является оптимальным решением для 3-х купонов, либо этот элемент перекрывается тремя основными вариантами выбора для 1-купонных элементов, и в этом случае вам необходимо найти наилучшую комбинацию одного из три лучших 1-купонных и 3-купонных.
3. с использованием 2 и 2. найдите 3 верхних 2 пункта. если # 1 и # 2 перекрываются, # 1 и # 3, если только они не перекрываются, в этом случае # 2 и # 3 не перекрываются.

этот ответ довольно расплывчатый .. Мне нужно больше обдумать его.

Answer 6

Эта проблема в принципе аналогична проблеме Командировщик , где O (n!) Является наилучшим для поиска оптимального решения. Есть несколько ярлыков, которые можно использовать, но они потребовали много-много времени, чтобы их обнаружить, и я сомневаюсь, что у вас есть.

Проверка каждой возможной комбинации будет наилучшим использованием вашего времени, при условии, что мы имеем дело с небольшим количеством купонов. Заставьте клиента немного подождать, вместо того, чтобы тратить на это годы.