c# – 最小化批量折扣订单的价格

发布时间：2020-12-15 08:27:22 所属栏目：百科来源：网络整理

导读：我正在尝试整合一个系统,根据要求的数量建议消耗品套件.我遇到的挑战是套件具有批量/批量折扣,因此客户订购更大数量的价格可能更便宜,因为价格可能更低.例如,假设可用的工具包是： 25个小部件,15美元 7个小部件,价格为7美元 5个小部件,4美元 1美元的小部件

我正在尝试整合一个系统,根据要求的数量建议消耗品套件.我遇到的挑战是套件具有批量/批量折扣,因此客户订购更大数量的价格可能更便宜,因为价格可能更低.例如,假设可用的工具包是：

> 25个小部件,15美元
7个小部件,价格为7美元
> 5个小部件,4美元
1美元的小部件

现在,对于请求的数量74,我的算法将建议2 x 25,2 x 10和4 x 1 = $48.然而,对于客户来说订购3 x 25 = 45美元会更便宜.

有关如何解决这个问题的任何想法？我在C#中编码.

谢谢！

解决方法

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

// bestPrice is array of best prices for each amount
// initially it's [0,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];
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!