首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >批量折扣订单的最低价格

问批量折扣订单的最低价格
EN

Stack Overflow用户
提问于 2010-08-16 18:04:52
回答 3查看 902关注 0票数 6

我正试图建立一个系统,根据所要求的数量来建议消耗品包。我遇到的挑战是,这些套件有批量/批量折扣,因此,由于价格可能较低,客户订购更大数量的商品可能会更便宜。例如,假设可用的工具包是:

  • 25小部件为$15
  • 10小部件为$7
  • 5小部件为$4
  • 1小部件为$1

现在,对于要求的74,我的算法将建议2x25,2x10和4x1=48美元。不过,顾客只需订购3x25=45美元就更便宜了。

对如何处理这件事有什么想法吗?我在用C#编码。

谢谢!

EN

回答 3

Stack Overflow用户

回答已采纳

发布于 2010-08-16 18:20:15

这看起来像标准的DP (动态编程)。

代码语言:javascript
复制
// 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数量的包的大小。我想,你可以弄清楚如何更新上面的伪代码。

一旦算法完成,您就可以得到这样的解决方案

代码语言:javascript
复制
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];
}
票数 7
EN

Stack Overflow用户

发布于 2010-08-16 18:42:51

因此,您实际上必须手动确定项目的所有断点,其顺序为25。然后,基本上使用查找表类型场景来确定qty小于25的订单。正如前面指出的,这与背包问题非常相似。

基本上,您的代码看起来类似于;

代码语言:javascript
复制
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

你可以用某种贪婪的算法来判断它。这将是理想的,如果价格预计会有很大的变化。

这看起来就像用一个精确的匹配来填充包大小,然后确定最接近的匹配,就在剩余的数量之上,看看它是否更便宜。

例如:

代码语言:javascript
复制
//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;
}

这段代码没有接近完成的地方,但应该给你一个想法。代码也可能不是最好的。

编辑

第二个代码块将在第一个块之后而不是查找。

票数 3
EN

Stack Overflow用户

发布于 2010-08-16 18:10:23

嗯,从第25单元开始,价格是每件0.60美元。因此,如果客户订单超过25,忘记您正在计算的软件包,只需将数量乘以0.60美元即可。

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/3495916

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档