Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1006647
  • 博文数量: 150
  • 博客积分: 3017
  • 博客等级: 少校
  • 技术积分: 3829
  • 用 户 组: 普通用户
  • 注册时间: 2011-11-19 14:40
个人简介

Now in Baidu WISE team

文章分类

全部博文(150)

文章存档

2014年(8)

2013年(31)

2012年(111)

分类: C/C++

2012-10-22 16:41:54

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


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

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


没看书上解法写出了自己的解法...然后再看书上的解法我没看懂,看起来好复杂的样子, 求大神给我解释一下书上的解法什么意思...以下是我的解法,如果有问题请重重的拍.


点击(此处)折叠或打开

  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <memory.h>
  4. #define MAX 10000
  5. #define MAXBOOK 10


  6. typedef struct tagNode{
  7.     int book[5];
  8.     int discount;
  9.     int size;
  10. } Node;
  11. int sales[6] = {0 ,0, 5 ,10, 20, 25};
  12. Node *result[MAX] = {NULL};
  13. void outputnode(Node * node){
  14.     printf("book0:[%d] book1:[%d] book2:[%d] book3:[%d] book4:[%d] discount: %d size: %d\n",node->book[0],node->book[1],node->book[2],node->book[3],node->book[4],node->discount,node->size);
  15. }
  16. int initialize(){
  17.     int ri = 0;
  18.     result[ri] = (Node *)malloc(sizeof(Node));
  19.     result[ri]->book[0] = 0;
  20.     result[ri]->book[1] = 0;
  21.     result[ri]->book[2] = 0;
  22.     result[ri]->book[3] = 0;
  23.     result[ri]->book[4] = 0;
  24.     result[ri]->discount = 0;
  25.     result[ri]->size = 0;
  26.     return 1;
  27. }
  28. int isEqual(Node * a, Node* b){
  29.     if(a->size!=b->size) return 0;
  30.     int i = 0;
  31.     for(;i<5;i++){
  32.         if(a->book[i] != b->book[i]) return 0;
  33.     }
  34.     return 1;
  35. }
  36. void replacenode(Node *src, Node*dest){
  37.     free(src);
  38.     src = dest;
  39. }
  40. void caldiscount(Node * tar){
  41.     int bi = 0;
  42.     int discount = 0;
  43.     for(;bi<5;bi++){
  44.         tar->book[bi] >5 ? (discount+= tar->book[bi]*sales[5]) : (discount+= tar->book[bi]*sales[tar->book[bi]]);
  45.     }
  46.     tar->discount = discount;

  47. }

  48. int main(){
  49.     int scopecount = 1;
  50.     initialize();
  51.     int bi = 0;
  52.     for(;bi<5;bi++){
  53.         int bicount = 2;
  54.         for(;bicount<=5;bicount++){
  55.             // printf("-----------result count: %d add %d book [%d] ---------\n",scopecount,bicount,bi);
  56.             int rc = 0;
  57.             int tmax = scopecount;
  58.             for(;rc<tmax;rc++){
  59.                 if(result[rc] == NULL) break;
  60.                 if(result[rc]->size + bicount>MAXBOOK) continue;
  61.                 Node * tmp = (Node*)malloc(sizeof(Node));
  62.                 memcpy(tmp, result[rc], sizeof(Node));
  63.                 tmp->book[bi]+=bicount;
  64.                 tmp->size+=bicount;
  65.                 //
  66.                 //tmp->discount += sales[bicount];
  67.                 caldiscount(tmp);
  68.                 //
  69.                 int t = 0;
  70.                 char isdup = 0;
  71.                 for(;t<MAX;t++){
  72.                     if(result[t]!= NULL && isEqual(result[t], tmp) == 1 && result[t]->discount< tmp->discount){
  73.                         isdup = t;
  74.                         break;
  75.                     }
  76.                 }
  77.                 if(isdup != 0){
  78.                     //replacenode(result[t],tmp);
  79.                     free(result[t]);
  80.                     result[t] = tmp;
  81.                     //    printf("replace:");
  82.                     //    outputnode(result[t]);
  83.                 }
  84.                 else{

  85.                     result[scopecount] = tmp;
  86.                     //    printf("base on result %d add: %d",rc, scopecount);
  87.                     //    outputnode(result[scopecount]);
  88.                     scopecount++;
  89.                 }
  90.             }
  91.         }
  92.     }
  93.     int p = 0;
  94.     int maxid = 0;
  95.     for(;p<MAX;p++){
  96.         if(result[p] == NULL) break;
  97.         if(result[p]->size == MAXBOOK && result[p]->discount>result[maxid]->discount)
  98.             maxid = p;
  99.     }

  100.     outputnode(result[maxid]);
  101.     return 1;
  102. }


阅读(849) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~