编程之美中的买书最优惠问题

买书问题常数时间空间解法
服务器君一共花费了364.248 ms进行了5次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

题目:在节假日的时候,书店一般都会做促销活动。由于《哈利波特》系列相当畅销,店长决定通过促销活动来回馈读者。在销售的《哈利波特》平装本系列中,一共有五卷,用编号0, 1, 2, 3, 4来表示。假设每一卷单独销售均需要8欧元。如果读者一次购买不同的两卷,就可以扣除5%的费用,三卷则更多。假设具体折扣的情况如下:

本数          折扣
2          	5%
3          	10%
4           20%
5           25%

在一份订单中,根据购买的卷数以及本书,就会出现可以应用不同折扣规则的情况。但是,一本书只会应用一个折扣规则。比如,读者一共买了两本卷一,一本卷二。那么,可以享受到5%的折扣。另外一本卷一则不能享受折扣。如果有多种折扣,希望能够计算出的总额尽可能的低。

要求根据这样的需求,设计出算法,能够计算出读者所购买一批书的最低价格。

分析:

首先假设五册书分别为A,B,C,D,E,不失一般性可以假设Na>=Nb>=Nc>=Nd>=Ne,设所有书可以划分为k组,每组中书不重复,则在最优解中有如下性质:

  1. 所有只包含一本书的组均只包含同一本书
  2. 若有两组包含一本书的组包含的书不同,则这两组合并,能得到更优解,与最优解矛盾.

  3. 包含一本书的组只包含A
  4. 若包含书为A',若Na'==Na,则A,A'对调即可,若Na'<Na,则必存在某组包含A不包含A',则将只包含A'的组并入该组能得到更优解。

  5. 所有只包含两本书的组均包含相同两本书
  6. 组(A', B'), (A',C')折扣0.2重组为(A',B',C')与(A)折扣0.3

  7. 包含两本书的组必包含A
  8. 若存在包含一本A的组,而两本书的组不包含A,则合并能得更优解。若不存在包含一本A的组,而两本书组包含为A',A'',则包含三本书,四本组必含A而缺A'者。(A', A''), (AXY), 折扣0.4不如(A''),(AXYA')0.8。(A',A''),(AXYZ)折扣0.9不如(A''),(AXYZA')1.25。

  9. 包含两本书的组必包含B
  10. 同上证。

  11. 所有只包含三本书的组均包含相同三本书
  12. (A,B,C),(A,B,D)折扣0.6,(A,B),(A,B,C,D)折扣0.9

  13. 所有包含三本书的组均包含A
  14. 若存在只包含A的组,合并得更优。若存在只包含A, B的组(A,B)(XYZ)折扣0.4,不如(B)(AXYZ)折扣0.8。若不存在一,二本组,假设三本书组为(X,Y,Z),则必有包含A的四本组缺X,(X,Y,Z)(A,A',A'',A''')折扣1.1,不如(Y,Z),(A,A',A'',A''',X)折扣1.35

  15. 所有包含三本的组均包含B,C
  16. 同上可证

  17. 所有包含四本书的组均包含A,B,C
  18. 设XYZW为(ABC)(BCDE)折扣1.1,不如(B,C),(A,B,C,D,E)折扣1.35。其它情况同理可证。

  19. 包含五本书与包含三本书情况不会同时出现
  20. (A,B,C),(A,B,C,D,E)折扣1.55,不如(A,B,C,D),(A,B,C,E)折扣1.6

由以上证明可得如下结论:

  • 每组均包含A,所有组数与A相同
  • 所有包含两本及以上的组均包含B,组数与B同
  • 所有包含三本及以上的组均包含C,组数与C同
  • 三,五不并存

由此可得解法如下:

const double BuyBook::UNIT_PRICE = 8;
const double BuyBook::DISCOUNTS[5] = {1, 0.95, 0.9, 0.8, 0.75};
static const int BOOK_KINDS = 5;
double BuyBook::SearchFast(int* books)
{
    Sort(books);
    int g[5];
    g[0] = books[0] - books[1];
    g[1] = books[1] - books[2];
    g[2] = books[2] - books[3];
    g[3] = books[3] - books[4];
    g[4] = books[4];
    int t = min(g[2], g[4]);
    if (t > 0)
    {
        g[2] -= t;
        g[4] -= t;
        g[3] += 2 * t;
    }
    double sum = 0;
    for (int i = 0; i < BOOK_KINDS; ++i)
    {
        sum += g[i] * (i+1) * UNIT_PRICE * DISCOUNTS[i];
    }
    return sum;
}

本文地址:http://www.nowamagic.net/librarys/veda/detail/966,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/966

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《JavaScript DOM编程艺术(第2版)》 基思(Jeremy Keith) (作者), 桑布尔斯(Jeffrey Sambells) (作者), 魏忠 (合著者), 杨涛 (译者), 王建桥 (译者), 杨晓云 (译者), 等 (译者)

《JavaScript DOM编程艺术(第2版)》内容简介:JavaScript是Web开发中最重要的一门语言,它强大而优美。无论是桌面开发,还是移动应用。JavaScript都是必须掌握的技术。W3C的DOM标准是开发Web应用的基石。已经得到所有现代浏览器的支持,这使得跨平台Web开发成了一件轻松惬意的事。《JavaScript DOM编程艺术(第2版)》是超级畅销书的升级版,由倡导Web标准的领军人物执笔,揭示了前端开发的真谛,是学习JavaScript和DOM开发的必读之作。

更多计算机宝库...