一道好难的算法题求大家帮忙

落星桀

计算随购买数量而变的折扣书的金额

题目描述：
        从前有一套5册的系列书，是关于一个名叫“Harry”的英国英雄的（起码在该问题出现时还只有5本，但之后又出了无数本）。全世界的儿童都认为他非常了不起，自然，出版商也这么认为。作为一种对全人类的无比慷慨的姿态，（以及为了提高销量），出版商制定了下述标价模型，来充分利用Harry的魔力：
5册书的任何1本的价格为8欧元。
如果你购买2本不同的书，你可以得到5%的折扣。
如果你购买3本不同的书，你可以得到10%的折扣。
如果你购买4本不同的书，你可以得到20%的折扣。
如果你购买整个系列，你可以得到25%的折扣。
如果你购买4本书，其中3本书是不同的，那么对那3本书，你可以得到10%的折扣，但第4本的价格仍然是原价8欧元。
        Potter狂热席卷全国，各地少年儿童的父母装着满车的Potter书在柜台外排起了长队。。。你的任务是写段代码，计算每个购物车的金额，尽可能给与最大折扣。
        譬如，这个购物车里的图书算多少钱？ 第一册书有2本第二册书有2本第三册书有2本第四册书有1本第五册书有1本 （答案是 51.20 欧元）。 求如何用Python实现

落星桀

怎么没人喽

牡丹花下死做鬼

难得不是编程是数学     

微逻辑

落星桀 发表于 2015-1-2 07:50
怎么没人喽

写了一个，但结果和楼主的不一样，不知错在哪里。等高手。经楼主提醒，这个答案是错的，没这么简单。

1. def off(book_list):
   
2.     '''按列表中各元素的数量计算折扣并加到总价中'''
   
3.     global price
   
4.     book_num = len(book_list)
   
5.     discount = discount_rate[book_num]
   
6.     s = book_list.pop()
   
7.     price += s * discount * 8 * book_num
   
8.     if len(book_list) == 0:
   
9.         return
   
10.     for i in range(len(book_list)):
    
11.         book_list[i] -= s
    
12.         if book_list[i] < 0:
    
13.             book_list[i] = 0
    
14.     off(book_list)
    
15. 
    
16. 
    
17. book_list = []
    
18. discount_rate = {5:(1-0.25),4:(1-0.2),3:(1-0.1),2:(1-0.05),1:1} #折扣率
    
19. for i in range(5):
    
20.     number = input('第%s本书的数量：' % (i+1))
    
21.     book_list.append(int(number))
    
22. book_list.sort(reverse = True)
    
23. price = 0
    
24. off (book_list)
    
25. print('总价{:1.2f}欧元' .format(price))

复制代码

爱琴海里的星

嗯嗯~{:1_1:}楼上对吧。。。

落星桀

最后需要求的那种情况是分为两个4本不同最便宜，而不是5本不同和3本不同

落星桀

微逻辑 发表于 2015-1-2 12:12
写了一个，但结果和楼主的不一样，不知错在哪里。等高手。

题目最后需要求的那种购书情况，是要分成两个买了4本不同书，而不是5本不同和3本不同

微逻辑

落星桀 发表于 2015-1-2 13:18
题目最后需要求的那种购书情况，是要分成两个买了4本不同书，而不是5本不同和3本不同

明白了。我想也不会那么简单。

wei_Y

写完了，那个，呃……效率有点低。自己优化优化吧。

1. import itertools
   
2. 
   
3. def pay(book):
   
4.         pay_money = []
   
5.         discount = [1,1,0.95,0.9,0.8,0.75]   #折扣
   
6.         def inter(books,sums=[]):
   
7.                 if len(books) == 0:      #原理和快排差不多，分到最后就出来了。
   
8.                         pay_money.append(sum(sums))     #将总数插到需支付的列表里。
   
9.                 for i in range(1,6):     #从1开始，这里应该可以优化。
   
10.                         temp = itertools.combinations(books,i)    #从购书的列表里组合出不同的组合。长度就是 i.
    
11.                         for j in temp:       #加了这步就会慢了。将所有的组合的钱算一下。
    
12.                                 temp1 = books[:]
    
13.                                 for c in j:      #将已经花了钱的减去。
    
14.                                         temp1.remove(c)
    
15.                                 inter(temp1,sums=sums+[(8*len(j))*discount[len(set(j))]])
    
16.                                 #在sums钱里加上已经支付的钱。如果book列表里没有书了，那就会到pay_money里。
    
17.                                 #思路就是快排的思路，一层层的往下分。
    
18.                                 #但是递归本身慢，而且还是嵌套的两层循环。
    
19.                                 #效率不高效。
    
20.         inter(book)
    
21.         return min(pay_money)   #可以改的人性化点。
    
22. 
    
23. book = []
    
24. for i in range(1,6):
    
25.         list1 = int(input('需求的数量，从第一册开始。'))
    
26.         for j in range(list1):
    
27.                 book.append(i)
    
28. print(pay(book))

复制代码

微逻辑

wei_Y 发表于 2015-1-2 15:38
写完了，那个，呃……效率有点低。自己优化优化吧。

学习了，虽然还看不懂。

落星桀

wei_Y 发表于 2015-1-2 15:38
写完了，那个，呃……效率有点低。自己优化优化吧。

太感谢了，人间有真爱啊:cry

瞬秒爆加速

wei_Y 发表于 2015-1-2 15:38
写完了，那个，呃……效率有点低。自己优化优化吧。

佩服

小山童鞋

学C的，可以递归和递推,
不知道为什么有点误差。

1. 
   
2. #include<stdio.h>
   
3. #define PRICE 8          //每本书的价格
   
4. 
   
5. int books_number[5] = {0};//书的每本书的数量
   
6. double discount[5] = {PRICE,
   
7.                       PRICE * 0.95,
   
8.                       PRICE * 0.9,
   
9.                       PRICE * 0.8,
   
10.                       PRICE * 0.75};
    
11. 
    
12. double calculate()      //核心算法，递归解决
    
13. {
    
14.     int i = 0,k=0;
    
15.     double sum = 0;
    
16.     while(i<5)
    
17.     {
    
18.         if(0 != books_number[i])
    
19.         {
    
20.             books_number[i]--;
    
21.             k++;
    
22.         }
    
23.         i++;
    
24.     }
    
25.     if(0 == k)
    
26.         return 0;
    
27.     else
    
28.     {
    
29.         sum = discount[k-1] * k;
    
30.         return (sum + calculate());           //递归
    
31.     }
    
32. }
    
33. int main()
    
34. {
    
35.     int i;
    
36.     double sum = 0;
    
37.     printf("请分别输入五本书的数量\n");
    
38.     for(i=0;i<5;i++)
    
39.     {
    
40.         printf("books_number[%d] = ",i);
    
41.         scanf("%d",&books_number[i]);
    
42.     }
    
43. /*
    
44.     for(i=0;i<5;i++)
    
45.     {
    
46.         printf("books_number[%d] = %d\n",i,books_number[i]);
    
47.     }
    
48.     for(i=0;i<5;i++)
    
49.     {
    
50.         printf("discount[%d] = %f\n",i,discount[i]);
    
51.     }
    
52. */
    
53.     printf("\n你需要付的金额为: ");
    
54.     sum = calculate();
    
55.     printf("%f $\n",sum);
    
56.     system("pause");
    
57.     return 0;
    
58. }
    

复制代码

sweet兔

有意思哦