Минимизировать цену за объем заказы со скидками
Я пытаюсь собрать систему, которая будет предлагать расходные комплекты на основе запрошенного количества. Проблема, с которой я сталкиваюсь, заключается в том, что у комплектов есть скидки на объем / оптовую продажу, поэтому заказчику может быть дешевле заказать большее количество, потому что цена может быть меньше. Например, допустим, доступны следующие наборы:
- 25 виджетов за 15 долларов США
- 10 виджетов за 7 долларов США
- 5 виджетов за 4 доллара США
- 1 виджет за 1 доллар США
Прямо сейчас, для запрошенного количества 74 Мой алгоритм предложит 2 x 25, 2 x 10 и 4 x 1 = 48 долларов. Однако для клиента было бы дешевле просто заказать 3 x 25 = $ 45.
Есть мысли о том, как решить эту проблему? Я пишу на C #.
Спасибо!
3 ответа
Это похоже на стандартный DP (динамическое программирование).
// bestPrice is array of best prices for each amount
// initially it's [0, INFINITY, INFINITY, INFINITY, ...]
for (int i = 0; i <= 74; ++i) {
for (Pack pack : packs) {
// if (i + pack.amount) can be achieved with smaller price, do it
int newPrice = bestPrice[i] + pack.price;
if (newPrice < bestPrice[i + pack.amount]) {
bestPrice[i + pack.amount] = newPrice;
}
}
}
Ответ: мин (bestPrice [74], bestPrice [74 + 1], ... bestPrice [74 + 25 - 1]) . Накладные расходы 25 - 1 , очевидно, достаточно, потому что в противном случае вы удалили бы одну упаковку, и сумма все равно была бы > = 74 .
Некоторые ссылки по теме:
http://en.wikipedia.org/wiki/Dynamic_programming
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg
edit
Вы можете найти оптимальное решение, если немного его измените. Добавьте массив lastPack , так что lastPack [i] - это размер пакета, который вы использовали для достижения amount i . Думаю, вы можете понять, как обновить псевдокод выше.
После завершения алгоритма вы можете получить такое решение
int total = 74;
while (total > 0) {
// package of size lastPack[total] was used to get amount 'total'
// do whatever you want with this number here
total -= lastPack[total];
}
Итак, вам придется вручную определить все точки останова для элементов с порядковым номером 25. Затем, по сути, использовать сценарий типа таблицы поиска, чтобы определить, что заказывать для количества менее 25. Как указывалось ранее, это очень похоже на проблему ранца.
В основном ваш код будет выглядеть примерно так:
int qtyOrder;
int qtyRemain;
int qty25pack;
int qty10pack;
int qty5pack;
int qty1pack;
//Grab as many 25 packs as possible
qty25pack = (qtyOrder % 25);
qtyRemain -= qty25Pack * 25;
//Here use your lookup table to determine what to order
// for the qty's that are less than 25
Вы можете использовать какой-то жадный алгоритм, чтобы определить это на лету. Это было бы идеально, если ожидается, что цены будут часто меняться.
Это может выглядеть как заполнение размера упаковки точным совпадением, а затем определение ближайшего совпадения, которое чуть больше оставшегося количества и посмотреть, не будет ли оно дешевле.
Например:
//find the perfect product amount price
While (qtyRemain != 0) {
perfectPrice += (qtyRemain % nextSmallestSize) * nextSmallestPackagePrice;
qtyRemain -= (qtyReamin % nextSmallestSize)
}
//Find the closest match over price
While ((qtyRemain % nextSmallestSize) != 0){
closePrice += (qtyRemain % nextSmallestSize) * nextSmallestPackagePrice;
qtyRemain -= (qtyRemain % nextSmallestSize)
}
//add the last price before we reached the perfect price size
closePrice += nextSmallestPackagePrice;
//determine lowest price
if closePrice < perfectPrice {
cost = closePrice;
}
else {
cost = PerfectPrice;
}
Этот код не является практически полным, но должен дать вам представление. Код также, вероятно, не самый лучший.
Редактировать
Второй кусок кода будет идти после первого куска на месте поиска
Ну, начиная с 25-го, цена 0,60 $ / шт. Поэтому, если клиент заказывает более 25 пакетов, забудьте о пакетах, которые вы рассчитываете, и просто умножьте количество на 0,60 доллара.