> 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];}总结
以上是内存溢出为你收集整理的c# – 最小化批量折扣订单的价格全部内容,希望文章能够帮你解决c# – 最小化批量折扣订单的价格所遇到的程序开发问题。
如果觉得内存溢出网站内容还不错,欢迎将内存溢出网站推荐给程序员好友。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)