/*算法高手请进。有一个难题求解？
标准原材料长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;    /*返回原材料的数量*/
}     

评论