/*算法高手请进。有一个难题求解？ 标准原材料长600cm。 可能要截成以下几种规格：60cm、80cm、90cm、120cm、150cm、180cm、210cm、240cm的任意几种的组合。 比方说： 方案一：需要60cm28根、210cm16根、240cm8根，最少需要多少根原材料（600cm） 方案.... 此解主要解决怎么才能最省料。 另：能否解任意规格尺寸的问题。*/ /*算法；将材料规格按照从大到小的顺序从原材料中取出，这样最省料。 程序不但给出所需的原材料数量，还给出每根原材料剩下的边角余料。 通过改变M，N的值可以改变原材料的预计数量和所需材料的规格*/ /*2005-4-22 梁见斌*/ #include<stdio.h> #include<stdlib.h> #define N 8 #define M 100 int Input(void);/*输入材料的规格和数量*/ void sort(int len);/*将材料规格按照从大到小的顺序排列，以便处理*/ void print(int len);/*按顺序打印输入材料的规格和数量*/   int solve(int len);/*将材料规格按照从大到小的顺序从原材料中取出，这样最省料*/ /*wood[N][2]存储输入材料的规格和数量；source[M]存储原材料的数量；rest存储剩下边角余料*/ int wood[N][2], source[M], rest=0; int main(void) {    int kind, num;    kind = Input();/*kind表示输入材料规格的种类*/    sort(kind);    print(kind);    num = solve(kind);    printf("\n至少需要原材料%d根", num);    printf("\n剩下边角余料总共%d cm，具体的剩余情况为：\n", rest);    for(int i=0; i<num; i++)        printf("第%d根剩下%d cm\n", i+1, source[i]);    system("pause");    return 0; } int Input(void) {    int i=0;    do{       printf("请输入第 %d 种材料的规格和数量（输入0 0表示结束）", i+1);       scanf("%d%d", &wood[i][0], &wood[i][1]);    }  while(wood[i++][0] != 0 && i <= N );    return i-1; }       void sort(int len) {    int i, j, max, t;    for(i=0; i<len-1; i++)/*将材料规格按照从大到小的顺序排列*/    {       max = i;       for(j=i; j<len; j++)           if(wood[j][0] > wood[max][0])               max = j;          if(max != i)          {             t = wood[max][0];             wood[max][0] = wood[i][0];             wood[i][0] = t;             t = wood[max][1];             wood[max][1] = wood[i][1];             wood[i][1] = t;          }       }    } void print(int len) {    int i;    puts("您需要的材料规格和数量如下：");    for(i=0; i<len; i++)        printf("规格：%d cm     数量；%d 根\n", wood[i][0], wood[i][1]); }     int solve(int len) {    int i=0, j=0, s, m, Flag=0;    int sum[N]={0}, flag[N]={0};    for(int i=0; i<100; i++)        source[i] = 600;   /*每根原材料均长600cm*/       for(i=0; i<100; i++)       {          for(j=0; j<len; j++)/*将材料规格按照从大到小的顺序从原材料中取出，这样最省料*/          {             if(flag[j] == 0)/*如果第j种规格的材料数量还不够，继续从原材料中截取*/             {                while( source[i] >= wood[j][0] && sum[j] < wood[j][1])                {                   source[i] -= wood[j][0];                   sum[j]++;/*累计第j种规格的材料数量*/             }             if(sum[j] == wood[j][1])/*当第j种规格的材料数量足够时，令参数flag[j] = 1*/                 flag[j] = 1;          }             }       rest += source[i];/*累计边角余料*/       for( s=0, m=0; m<len; m++)/*累计所有规格的材料数量的参数，判断是否所有规格的材料数量都够了*/           s += flag[m];       if( s == len)/*若所有规格的材料数量都够了，则工作结束，退出循环*/           Flag=1;             if(Flag == 1)              break;           }      return i+1;    /*返回原材料的数量*/ }     

评论