- 浏览: 21247 次
- 性别:
- 来自: 南京
最新评论
买书折扣最优惠问题解法
- 博客分类:
- 算法
题目:在节假日的时候,书店一般都会做促销活动。由于《哈利波特》系列相当畅销,店长决定通过促销活动来回馈读者。在销售的《哈利波特》平装本系列中,一共有五卷,用编号0, 1, 2, 3, 4来表示。假设每一卷单独销售均需要8欧元。如果读者一次购买不同的两卷,就可以扣除5%的费用,三卷则更多。假设具体折扣的情况如下:
view sourceprint?1 本数 折扣
2 2 5%
3 3 10%
4 4 20%
5 5 25%
在一份订单中,根据购买的卷数以及本书,就会出现可以应用不同折扣规则的情况。但是,一本书只会应用一个折扣规则。比如,读者一共买了两本卷一,一本卷二。那么,可以享受到5%的折扣。另外一本卷一则不能享受折扣。如果有多种折扣,希望能够计算出的总额尽可能的低。
要求根据这样的需求,设计出算法,能够计算出读者所购买一批书的最低价格。
分析:
首先假设五册书分别为A,B,C,D,E,不失一般性可以假设Na>=Nb>=Nc>=Nd>=Ne,设所有书可以划分为k组,每组中书不重复,则在最优解中有如下性质:
所有只包含一本书的组均只包含同一本书
若有两组包含一本书的组包含的书不同,则这两组合并,能得到更优解,与最优解矛盾.
包含一本书的组只包含A
若包含书为A',若Na'==Na,则A,A'对调即可,若Na'<Na,则必存在某组包含A不包含A',则将只包含A'的组并入该组能得到更优解。
所有只包含两本书的组均包含相同两本书
组(A', B'), (A',C')折扣0.2重组为(A',B',C')与(A)折扣0.3
包含两本书的组必包含A
若存在包含一本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。
包含两本书的组必包含B
同上证。
所有只包含三本书的组均包含相同三本书
(A,B,C),(A,B,D)折扣0.6,(A,B),(A,B,C,D)折扣0.9
所有包含三本书的组均包含A
若存在只包含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
所有包含三本的组均包含B,C
同上可证
所有包含四本书的组均包含A,B,C
设XYZW为(ABC)(BCDE)折扣1.1,不如(B,C),(A,B,C,D,E)折扣1.35。其它情况同理可证。
包含五本书与包含三本书情况不会同时出现
(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同
三,五不并存
由此可得解法如下:
view sourceprint?01 const double BuyBook::UNIT_PRICE = 8;
02 const double BuyBook::DISCOUNTS[5] = {1, 0.95, 0.9, 0.8, 0.75};
03 static const int BOOK_KINDS = 5;
04 double BuyBook::SearchFast(int* books)
05 {
06 Sort(books);
07 int g[5];
08 g[0] = books[0] - books[1];
09 g[1] = books[1] - books[2];
10 g[2] = books[2] - books[3];
11 g[3] = books[3] - books[4];
12 g[4] = books[4];
13 int t = min(g[2], g[4]);
14 if (t > 0)
15 {
16 g[2] -= t;
17 g[4] -= t;
18 g[3] += 2 * t;
19 }
20 double sum = 0;
21 for (int i = 0; i < BOOK_KINDS; ++i)
22 {
23 sum += g[i] * (i+1) * UNIT_PRICE * DISCOUNTS[i];
24 }
25 return sum;
26 }
view sourceprint?1 本数 折扣
2 2 5%
3 3 10%
4 4 20%
5 5 25%
在一份订单中,根据购买的卷数以及本书,就会出现可以应用不同折扣规则的情况。但是,一本书只会应用一个折扣规则。比如,读者一共买了两本卷一,一本卷二。那么,可以享受到5%的折扣。另外一本卷一则不能享受折扣。如果有多种折扣,希望能够计算出的总额尽可能的低。
要求根据这样的需求,设计出算法,能够计算出读者所购买一批书的最低价格。
分析:
首先假设五册书分别为A,B,C,D,E,不失一般性可以假设Na>=Nb>=Nc>=Nd>=Ne,设所有书可以划分为k组,每组中书不重复,则在最优解中有如下性质:
所有只包含一本书的组均只包含同一本书
若有两组包含一本书的组包含的书不同,则这两组合并,能得到更优解,与最优解矛盾.
包含一本书的组只包含A
若包含书为A',若Na'==Na,则A,A'对调即可,若Na'<Na,则必存在某组包含A不包含A',则将只包含A'的组并入该组能得到更优解。
所有只包含两本书的组均包含相同两本书
组(A', B'), (A',C')折扣0.2重组为(A',B',C')与(A)折扣0.3
包含两本书的组必包含A
若存在包含一本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。
包含两本书的组必包含B
同上证。
所有只包含三本书的组均包含相同三本书
(A,B,C),(A,B,D)折扣0.6,(A,B),(A,B,C,D)折扣0.9
所有包含三本书的组均包含A
若存在只包含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
所有包含三本的组均包含B,C
同上可证
所有包含四本书的组均包含A,B,C
设XYZW为(ABC)(BCDE)折扣1.1,不如(B,C),(A,B,C,D,E)折扣1.35。其它情况同理可证。
包含五本书与包含三本书情况不会同时出现
(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同
三,五不并存
由此可得解法如下:
view sourceprint?01 const double BuyBook::UNIT_PRICE = 8;
02 const double BuyBook::DISCOUNTS[5] = {1, 0.95, 0.9, 0.8, 0.75};
03 static const int BOOK_KINDS = 5;
04 double BuyBook::SearchFast(int* books)
05 {
06 Sort(books);
07 int g[5];
08 g[0] = books[0] - books[1];
09 g[1] = books[1] - books[2];
10 g[2] = books[2] - books[3];
11 g[3] = books[3] - books[4];
12 g[4] = books[4];
13 int t = min(g[2], g[4]);
14 if (t > 0)
15 {
16 g[2] -= t;
17 g[4] -= t;
18 g[3] += 2 * t;
19 }
20 double sum = 0;
21 for (int i = 0; i < BOOK_KINDS; ++i)
22 {
23 sum += g[i] * (i+1) * UNIT_PRICE * DISCOUNTS[i];
24 }
25 return sum;
26 }
发表评论
-
KMP快速字符串查找算法
2011-08-25 19:29 640在C/C++语言编程过程中,一般的字符串搜索操作都是通过标准库 ... -
求解最大公约数问题
2011-08-25 19:27 662最大公因数,又称最大公约数。是指 [n(≧2)个自然数 a1, ... -
堆排序(Heap Sort)算法学习
2011-08-25 19:26 1058在程序设计相关领域, ... -
整数拆分问题的动态规划解法
2011-08-25 19:26 3034输入n,和k,问将n用1到k这k个数字进行拆分,有多少种拆分方 ... -
背包问题介绍与分析
2011-08-25 19:24 1001背包问题是在1978年由Merkel和Hellman提出的。它 ... -
求平方根sqrt()函数的底层算法效率问题
2011-08-25 19:23 1264我们平时经常会有一些数据运算的操作,需要调用sqrt,exp, ... -
面试中常见的一些算法问题
2011-08-25 19:22 672Problem 1 : Is it a loop ? ( ... -
各种排序算法的C++实现与性能比较
2011-08-25 19:21 891排序是计算机算法中非常重要的一项,而排序算法又有不少实现方法, ... -
背包问题之硬币找零问题
2011-08-25 19:19 1129设有6 种不同面值的硬 ... -
求能被1到20的数整除的最小正整数
2011-08-25 19:18 1338求能被1到20的数整除的最小正整数。最直觉的方法是求1到20这 ... -
二叉树中的最近公共祖先问题
2011-08-25 19:16 1293题目:要求寻找二叉树中两个节点的最近的公共祖先,并将其返回。 ... -
判断一个整数是否是2的N次方
2011-08-25 19:04 1789题目:给定一个整数num,判断这个整数是否是2的N次方。比如, ... -
字符串逆序的算法汇总
2011-08-25 19:01 1034很早就准备写一个字符串系列的面试题,本来已经写好了,大概有十几 ... -
计算从1到N中1的出现次数
2011-08-25 18:59 574给定一个十进制整数N, ... -
KMP快速字符串查找算法
2011-08-25 18:57 939在C/C++语言编程过程中,一般的字符串搜索操作都是通过标准库 ... -
快速排序的递归实现
2011-08-25 18:54 728快速排序是对冒泡排序的一种改进。它的基本思想是:通过一次排序将 ... -
数字1亿里面有多少个1呢
2011-08-25 18:52 710乍看这题真够唬人的,群里看到这个题目后争先恐后的说看法。最简单 ... -
最大子序列、最长公共子串、最长公共子序列
2011-08-25 18:33 755最大子序列 最大子序列是要找出由数组成的一维数组中和最大的连续 ... -
一道关于男女比例的面试题
2011-08-25 16:56 1016阿里巴巴的一道面试题:说澳大利亚的父母喜欢女孩,如果生出来的第 ...
相关推荐
主元素问题解法4.rar 主元素问题解法4.rar 主元素问题解法4.rar 主元素问题解法4.rar 主元素问题解法4.rar 主元素问题解法4.rar 主元素问题解法4.rar 主元素问题解法4.rar 主元素问题解法4.rar 主元素问题解法4.rar ...
问题解法 微积分学辞典
反问题的数值解法.pdf图书。肖庭延、于慎根、王彦飞著,科学出版社,274页。
主元素问题解法1.rar 主元素问题解法1.rar 主元素问题解法1.rar 主元素问题解法1.rar 主元素问题解法1.rar 主元素问题解法1.rar 主元素问题解法1.rar 主元素问题解法1.rar 主元素问题解法1.rar 主元素问题解法1.rar ...
主元素问题解法5.rar 主元素问题解法5.rar 主元素问题解法5.rar 主元素问题解法5.rar 主元素问题解法5.rar 主元素问题解法5.rar 主元素问题解法5.rar 主元素问题解法5.rar 主元素问题解法5.rar 主元素问题解法5.rar ...
主元素问题解法3.rar 主元素问题解法3.rar 主元素问题解法3.rar 主元素问题解法3.rar 主元素问题解法3.rar 主元素问题解法3.rar 主元素问题解法3.rar 主元素问题解法3.rar 主元素问题解法3.rar 主元素问题解法3.rar ...
数位计数问题解法研究.pdf
博弈问题的解法.rar
主元素问题解法2.rar 主元素问题解法2.rar 主元素问题解法2.rar 主元素问题解法2.rar 主元素问题解法2.rar 主元素问题解法2.rar 主元素问题解法2.rar 主元素问题解法2.rar 主元素问题解法2.rar 主元素问题解法2.rar ...
二维稳态导热问题数值解法.pdf
用于自动寻找迷宫路径,可自已输入地图
主要讲解不适定问题以及各种解法,是数值分析的基础知识,特别有用!
八皇后问题的两种解法,包含c方式和c++方式
背包问题的各种解法,以及背包问题的一些推导过程,再加上扩展的背包问题,很不错的教程
用C#实现迷宫路径问题的两种解法:广度优先搜索和递归搜索。其中包含三个类:迷宫类,双向队列类和主Form类。两种搜索方式均封装在迷宫类中。
热传导问题的数值解法zip,热传导问题的数值解法
阶微分方程初值问题的数值解法高阶微分方程初值问题的数值解法高阶微分方程初值问题的数值解法
常微分方程初值问题数值解法.ppt
第4章 静态场边值问题的解法第4章 静态场边值问题的解法