TXT

ID2 of Baidu

By Harold Morris,2014-10-30 16:42
9 views 0
ID2 of Baidu

ID2 of Baidu

#include <stdio.h>

    #include <stdlib.h>

    #include <math.h>

    #define MAX 1000

     int N, M ,K;// 0<N<=16,0<M<=N;0<K<=12

     int ordered[17];

     int tempordered[17];

     double currDer, bestDer;

     char name[18][22]; //菜的名字

     int value[20][4]; //菜的价格

     int needed[5]; //需要的菜的数目

int OK(){

     int i;

     for(i = 1; i<=4; i++)

     {

     if(needed[i] < 0)return -1;

     }

     return 0;

    }

int testGoal(){

     int i;

     for(i = 1; i<=4; i++)

     {

     if( needed[i] != 0 )

     return -1;

     }

     return 0;

    }

void Backtrack(int depth, int num )

    {

     int i;

     double temp;

     int tempsum;

     if((num == M) && (testGoal() == 0) && (depth <= N +1)){

     //------计算当前偏差

     tempsum = 0;

     for(i = 1; i < N +1; i++){

     if(tempordered[i] == 1) tempsum += value[i][1];

     }

     currDer = (tempsum - 15* K) / K;

     //for(i = 1; i < N+1; i++)printf("%d ",tempordered[i]);

     //printf("\n");

     //------计算完毕

     if(fabs(currDer) < fabs(bestDer))

     {

     temp = currDer ;

     currDer = bestDer;

     bestDer = temp;

     for(i = 1; i < N +1; i++)ordered[i] = tempordered[i];

     // printf("the best is %f\n", bestDer);

     }

     }

     else{

     if( (OK() == 0) && (depth <= N +1))

     {

     tempordered[depth] = 1;

     //减去needed[]中对应的荤素辣淡数目

     if(value[depth][2] == 1)needed[1]--;

     if(value[depth][2] == 0)needed[2]--;

     if(value[depth][3] == 1)needed[3]--;

     if(value[depth][3] == 0)needed[4]--;

     Backtrack(depth + 1, num +1); //注意下面的BTnum 不加 1

     //恢复needed[]中对应的荤素辣淡数目

     if(value[depth][2] == 1)needed[1]++;

     if(value[depth][2] == 0)needed[2]++;

     if(value[depth][3] == 1)needed[3]++;

     if(value[depth][3] == 0)needed[4]++;

     tempordered[depth] = 0;

     Backtrack(depth + 1, num ); //

     }

     }

     return ;

    }

int main(int argc ,char * argv[]){

     int i,j;

     FILE *fp;

     fp = fopen(argv[1] ,"r");

     fscanf(fp, "%d %d %d", &N, &M, &K);

     i = N;

     for(i=1 ; i<=N; i++)

     {

     fscanf(fp ,"%s", &name[i][0]);

     fscanf(fp, "%d %d %d", &value[i][1] , &value[i][2], &value[i][3]);

     }

     fscanf(fp, "%d %d %d %d",&needed[1], &needed[2], &needed[3], &needed[4]);

     fclose(fp);

     int num; //已经点了的菜的数目

     double sum = 0; //总的花费

     for(i=0; i<17; i++)

     {

     ordered[i] = 0;

     tempordered[i] = 0;

     }

     num = 0;

     bestDer = MAX;

     /*for(i = 1 ; i <= N; i++)

     {

     printf("%s %d %d %d \n", name[i], value[i][1], value[i][2],

     value[i][3]);

     }

     printf("%d %d %d %d",needed[1], needed[2], needed[3], needed[4]);

     */

     Backtrack(1, num);

     for(i = 1; i<N+1 ; i++)

     {

     if(ordered[i] == 1)sum += value[i][1];

     }

     for(i = 1; i<=N; i++)

     {

     if(ordered[i]==1){

     printf("%s\n", name[i]);

     }

     }

     printf("%.2f \n", sum / K * 0.8);

     return 0;

}

Report this document

For any questions or suggestions please email
cust-service@docsford.com