问题:
在节假日的时候,书店一般都会做促销活动。由于《哈利波特》系列相当畅销,店长决定通过促销活动来回馈读者。在销售的《哈利波特》平装本系列中,一共有五卷,用编号0, 1, 2, 3, 4来表示。假设每一卷单独销售均需要8欧元。如果读者一次购买不同的两卷,就可以扣除5%的费用,三卷则更多。假设具体折扣的情况如下:
本数 折扣
2 5%
3 10%
4 20%
5 25%
在一份订单中,根据购买的卷数以及本书,就会出现可以应用不同折扣规则的情况。但是,一本书只会应用一个折扣规则。比如,读者一共买了两本卷一,一本卷二。那么,可以享受到5%的折扣。另外一本卷一则不能享受折扣。如果有多种折扣,希望能够计算出的总额尽可能的低。
要求根据这样的需求,设计出算法,能够计算出读者所购买一批书的最低价格。
没看书上解法写出了自己的解法...然后再看书上的解法我没看懂,看起来好复杂的样子, 求大神给我解释一下书上的解法什么意思...以下是我的解法,如果有问题请重重的拍.
- #include <stdlib.h>
- #include <stdio.h>
- #include <memory.h>
- #define MAX 10000
- #define MAXBOOK 10
- typedef struct tagNode{
- int book[5];
- int discount;
- int size;
- } Node;
- int sales[6] = {0 ,0, 5 ,10, 20, 25};
- Node *result[MAX] = {NULL};
- void outputnode(Node * node){
- 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);
- }
- int initialize(){
- int ri = 0;
- result[ri] = (Node *)malloc(sizeof(Node));
- result[ri]->book[0] = 0;
- result[ri]->book[1] = 0;
- result[ri]->book[2] = 0;
- result[ri]->book[3] = 0;
- result[ri]->book[4] = 0;
- result[ri]->discount = 0;
- result[ri]->size = 0;
- return 1;
- }
- int isEqual(Node * a, Node* b){
- if(a->size!=b->size) return 0;
- int i = 0;
- for(;i<5;i++){
- if(a->book[i] != b->book[i]) return 0;
- }
- return 1;
- }
- void replacenode(Node *src, Node*dest){
- free(src);
- src = dest;
- }
- void caldiscount(Node * tar){
- int bi = 0;
- int discount = 0;
- for(;bi<5;bi++){
- tar->book[bi] >5 ? (discount+= tar->book[bi]*sales[5]) : (discount+= tar->book[bi]*sales[tar->book[bi]]);
- }
- tar->discount = discount;
- }
- int main(){
- int scopecount = 1;
- initialize();
- int bi = 0;
- for(;bi<5;bi++){
- int bicount = 2;
- for(;bicount<=5;bicount++){
- // printf("-----------result count: %d add %d book [%d] ---------\n",scopecount,bicount,bi);
- int rc = 0;
- int tmax = scopecount;
- for(;rc<tmax;rc++){
- if(result[rc] == NULL) break;
- if(result[rc]->size + bicount>MAXBOOK) continue;
- Node * tmp = (Node*)malloc(sizeof(Node));
- memcpy(tmp, result[rc], sizeof(Node));
- tmp->book[bi]+=bicount;
- tmp->size+=bicount;
- //
- //tmp->discount += sales[bicount];
- caldiscount(tmp);
- //
- int t = 0;
- char isdup = 0;
- for(;t<MAX;t++){
- if(result[t]!= NULL && isEqual(result[t], tmp) == 1 && result[t]->discount< tmp->discount){
- isdup = t;
- break;
- }
- }
- if(isdup != 0){
- //replacenode(result[t],tmp);
- free(result[t]);
- result[t] = tmp;
- // printf("replace:");
- // outputnode(result[t]);
- }
- else{
- result[scopecount] = tmp;
- // printf("base on result %d add: %d",rc, scopecount);
- // outputnode(result[scopecount]);
- scopecount++;
- }
- }
- }
- }
- int p = 0;
- int maxid = 0;
- for(;p<MAX;p++){
- if(result[p] == NULL) break;
- if(result[p]->size == MAXBOOK && result[p]->discount>result[maxid]->discount)
- maxid = p;
- }
- outputnode(result[maxid]);
- return 1;
- }
阅读(849) | 评论(0) | 转发(1) |