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