Алгоритм ценовых скидок

Question

Я занимаюсь дизайном китайского аукциона.

Билеты (5, 10 и 20 долларов) продаются либо индивидуально, либо через пакеты для получения скидок. Существуют различные пакеты билетов, например:

1. 5- $ 5 билетов = получите скидку 10%
2. 5- $ 10 билетов = получите скидку 10%
3. 5- $ 20 билетов = получите скидку 10%
4. 5- $ 5 билетов + 5- $ 10 билетов + 5- $ 20 билетов = получите 15% скидку

Когда пользователи добавляют билеты в свою корзину, мне нужно найти самый дешевый пакет (ы), чтобы дать им. хитрость в том, что если пользователь добавляет 4-5 билетов + 5-10 долларов + 5-20 долларов, он все равно должен дать ему пакет № 4, так как это будет для него самым дешевым.

Любая помощь в выяснении алгоритма для решения этой проблемы, или любые советы будут очень признательны.

спасибо

EDIT

я разобрался с ответом, спасибо всем, но код длинный.

я опубликую код ответа, если кто-то еще заинтересован.

Answer 1

После продажи клиенту как можно большего количества готовых пакетов у нас остается несколько остаточных N билетов, требуемых для каждого из 3 типов (5, 10, 20 долларов). В приведенном вами примере желаемое количество варьируется от 0 до 5 (6 возможных значений). Таким образом, существует только 214 возможных остаточных комбинаций (6 ** 3 - 2; минус 2, потому что комбинации 0-0-0 и 5-5-5 вырождены). Просто предварительно рассчитайте цену каждой комбинации, как если бы она была куплена без пакета 4; сравните этот расчет со стоимостью пакета 4 (148,75 долл. США); это скажет вам самый дешевый подход для каждой комбинации.

Является ли фактическое количество пакетов настолько большим, что полное предварительное вычисление не будет приемлемым подходом?

Answer 2

Сначала подсчитайте, сколько вам нужно полного пакета 4.Уберите их с дороги.

full_package_4_count = min(x, y, z) mod 5.

x = x - 5 * full_package_4_count
y = y - 5 * full_package_4_count
z = z - 5 * full_package_4_count

Теперь, возможно, все же стоит купить еще несколько Пакетов 4, даже если они на самом деле не хотели покупать столько билетов.сколько из них может быть?

partial_package_4_max = (max(x, y, z) + 4) mod 5

Теперь цикл, чтобы попробовать каждый из них:

best_price = 10000000
for partial_package_4_count = 0 to partial_package_4_max:
    -- Calculate how much we have already spent.
    price = (full_package_4_count + partial_package_4_count) * 175 * (1-0.15)

    -- Work out how many additional tickets we want.
    x' = max(0, x - 5 * partial_package_count)
    y' = max(0, y - 5 * partial_package_count)
    z' = max(0, z - 5 * partial_package_count)

    --- Add cost for additional tickets (with a 10% discount for every pack of 5)
    price = price + x' mod 5 * 25 * (1-0.10) + x' div 5 * 5
    price = price + y' mod 5 * 50 * (1-0.10) + x' div 5 * 10
    price = price + y' mod 5 * 100 * (1-0.10) + x' div 5 * 20

    if price < best_price
        best_price = price
        -- Should record other details about the current deal here too.

Answer 3

Одним из подходов является динамическое программирование.

Идея состоит в том, что если покупателю нужны x элемента A, y элемента B и z элемента C, то вы должны вычислить все тройки (x ', y', z ') с 0 <= x' <= x и 0 <= y '<= y и 0 <= z' <= z самый дешевый способ получить хотя бы x 'из A, y' из B и z 'из C. Псевдокод: </p>

for x' = 0 to x
    for y' = 0 to y
        for z' = 0 to z
            cheapest[(x', y', z')] = min over all packages p of (price(p) + cheapest[residual demand after buying p])
            next_package[(x', y', z')] = the best package p

Затем вы можете вернуться назад (x, y, z), добавив в корзину пакеты, указанные в next_package.

Если есть много разных видов предметов или их много, лучше выбрать ветвь и границу.