求管材加工程序算法描述

Question

管材加工程序，要求如下：
设每根管材长度均为L，数量足够
现要切割成如下尺寸：
   长度（米）    数量（根）
     L1            N1
     L2            N2
             ：
             ： 
     Lm            Nm
如何切割最节省料
其中Lm<=L

Answer 1

看看源程序吧#include"stdafx.h"
#include <stdio.h>
#include <malloc.h>/*! 统计同种产品的生产次数，如果超过此种产品的产量，就跳到比他短的下个产品*/
int cn=1;    /*存放产品的链表*/
typedef struct list            
{  
/* len存放长度*/
int len;
/* num存放数量*/
int num; 

    struct list *next;
}ST;/*存放切割方法的链表*/
typedef struct rlist        
{  
/*times表示该产品用了几次*/
int len;
int num;
int times;                
    struct rlist *next;
}RST;/*函数接收输入的产品信息并升序排序存入链表*/
ST * init(int pRawLen)            
{    
int i = 1;
int input_len,input_num;    ST *head,*p,*t;
/*head是链表头结点，不存储信息*/
    head = (ST *)malloc(sizeof(ST));        
    head->next = NULL;
    p = head;
    printf("请输入需要加工成的产品的长度和数量：（输入0表示结束）\n");
    while(1)
    {   
printf("请输入第%d种长度：",i);
        scanf("%d", &input_len);
        printf("请输入第%d种数量：",i);
        scanf("%d", &input_num);
        if( (input_len == 0) || (input_num == 0) )
{
break;
}        if( (input_len > pRawLen) || (input_len <0 ) || (input_num <0 ) )
{
printf("长度或数量不正确！");
continue;
}        t = (ST *)malloc(sizeof(ST));
        t->len = input_len;
t->num = input_num;        while(1)
{
            if( (p->next != NULL) && (t->len > p->next->len))
            {   
t->next = p->next;
                p->next = t;
                break;
            }
            else if(p->next == NULL)
{
p->next = t;
t->next = NULL;
break;
}
            else
{
p = p->next;
}
}        p = head;
        i++;
    }    return head;
}void pr(ST *h)   /*输出产品列表*/
{   
while(h->next != NULL)
    {   
h = h->next;
printf("%d, %d\n", h->len, h->num);
}
}
/*寻找合适产品的函数，pRawLen是剩下的长度*/
RST* rselect(ST *h,int pRawLen, int pMillLen)       
{  
/*函数返回记录合适产品信息的链表指针*/
RST *r = NULL,*t;            
    ST *p,*k;    
    if(h == NULL)
{ 
/*如果到最后了还没找到合适结果，返回空*/
return NULL;       
}    for(k=p=h; p!=NULL && r==NULL; k=p,p=p->next)        
    {   
/*如果找到了，新建一个空间存放结果*/
if(p->len==pRawLen)                
        { 
r = (RST *)malloc(sizeof(RST));
            r->len = p->len;
            r->num = p->num;
            r->times = 1; 
            r->next = NULL;
            return r; /*返回该指针*/
} 

        if(p->len > pRawLen)
{
r = rselect(p->next, pRawLen, pMillLen);
if(r != NULL)
{
return r; /*如果材料不够，找更小的合适产品*/
}
}       
        else if((cn+1) > p->num)
{
cn = 1;
r = rselect(p->next, pRawLen-p->len-pMillLen, pMillLen);
}         
else
{
cn++;
/*判断剩余材料是否还能生产该产品*/
            r = rselect(p, pRawLen-p->len-pMillLen, pMillLen);

/*如果该产品被做过多次*/
            if( (r != NULL) && (r->len == p->len) )     
            {   
/*如果超出产品计划*/
if((r->times+1) > p->num)
{ 
if(r->len == h->len)
{
r = rselect(p->next, pRawLen-r->len-pMillLen, pMillLen);    /*找其他合适的组合*/
}
                    else
{
return NULL;
}
}
                else
{
r->times += 1;
return r;
}
}
}    /*否则就是找到一种方法*/
    } /*如果返回的结果是找到了，将本产品信息也保存在一起*/
    if(r  !=NULL)            
    {   
t = (RST *)malloc(sizeof(RST));
        t->len = k->len;
        t->num = k->num;
        t->times = 1;
        t->next = r;
        r = t;
    }    return r;
}/*输出一种结果*/
ST* hregulate(ST *h,RST *r)        
{   
RST *t = r->next;
    ST *p = h;
ST *k; /*c存放共用了几根材料*/
    int c = r->num/r->times;   

/*找出最小的就是c*/
    while(t != NULL)                
    {   
if(c > (t->num / t->times) )
{
c = t->num / t->times;
}        t = t->next;
}    printf("共用了材料%d根！\n",c); /*输出各种产品数量*/
    while(r != NULL)
    {   
printf("生产%d米产品%d根  ", r->len, c * r->times);
        
/*更新剩下产品数*/
while(p->next != NULL)  
        {    
if(r->len == p->next->len)
{ 
                if(p->next->num - c*r->times != 0)
                {   
p->next->num -= c*r->times;
                    p = p->next;
                    break;
}
                else 
                {   
k = p->next;
                    p->next = p->next->next;
                    free(k);
                    break;
                }
}
            p = p->next;
}
        r = r->next;
    }    cn = 1;
    return h;
}/*函数查找最优生产方法并输出*/
void product(ST *h,int pRawLen, int pMillLen)        
{   
ST *p,*k;
    RST *r;
    int i = 1;
int min;    while(h->next != NULL)
    {  
p = h; /*找到能全部利用材料的方法，输出*/
        if((r = rselect(p->next, pRawLen, pMillLen)) != NULL)      
        {   
printf("第%d种截取方法",i++);
            h = hregulate(p,r);
            printf("\n");
        }
        else
{
k = p;
            while(k->next != NULL)
{
k = k->next;
}            /*min存放未生产产品中长度最小的*/
min = k->len;  
            k = p; /*该循环将产品长度加上最小产品长度大于材料长度的产品输出*/
            while(pRawLen <= (k->next->len + min))  
            {   
r = (RST *)malloc(sizeof(RST));    
                r->len = k->next->len;
                r->num = k->next->num;
                r->times = 1;
                r->next = NULL;
                printf("第%d种截取方法", i++);
                h = k = hregulate(k, r);
                printf("\n");
                
/*全部做完了，退出*/
if(k->next == NULL)
{
return;
}
            } /*设定新的材料长度*/
pRawLen = pRawLen - 1;
         }
    }
}void main()
{
    int RawLen;
int MillLen;
    ST *st;    do
{
printf("请输入原材料长度：");
scanf("%d", &RawLen);
}while(RawLen <= 0); do
{
printf("请输入磨损度：");
scanf("%d", &MillLen);
}while(MillLen <= 0);    st = init(RawLen);
    pr(st);
    product(st, RawLen, MillLen);

int key;
printf("input enter key exit!\n");
scanf("%d", &key);
}