我正试图建立一个系统,根据所要求的数量来建议消耗品包。我遇到的挑战是,这些套件有批量/批量折扣,因此,由于价格可能较低,客户订购更大数量的商品可能会更便宜。例如,假设可用的工具包是:
现在,对于要求的74,我的算法将建议2x25,2x10和4x1=48美元。不过,顾客只需订购3x25=45美元就更便宜了。
对如何处理这件事有什么想法吗?我在用C#编码。
谢谢!
发布于 2010-08-16 18:20:15
这看起来像标准的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;
}
}
}答案是min(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
编辑
只要稍微修改一下,就可以找到最优的解决方案。添加lastPack数组,因此lastPack[i]是用于实现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];
}发布于 2010-08-16 18:42:51
因此,您实际上必须手动确定项目的所有断点,其顺序为25。然后,基本上使用查找表类型场景来确定qty小于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;
}这段代码没有接近完成的地方,但应该给你一个想法。代码也可能不是最好的。
编辑
第二个代码块将在第一个块之后而不是查找。
发布于 2010-08-16 18:10:23
嗯,从第25单元开始,价格是每件0.60美元。因此,如果客户订单超过25,忘记您正在计算的软件包,只需将数量乘以0.60美元即可。
https://stackoverflow.com/questions/3495916
复制相似问题