C语言——钢条切割——贪心算法

墨蓝 2023-06-17 06:57 20阅读 0赞

## 钢条切割 ##

这道题只是我刚开始学习线性规划的自己的根据大致做法自己写的代码。作为笔记记录一下，未必是简便的程序。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTIyNzQy_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTIyNzQy_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTIyNzQy_size_16_color_FFFFFF_t_70 2]

//贪心算法-----钢条切割 
    #include<stdio.h>
    typedef struct pole{
        float lenght;
        float price;
        float per;
    }Pole;
    
    
    int main(){
        int i,j,k,n,m,sum=0;
        Pole temp;
        
        Pole array[10]={
       {1,1},{2,5},{3,8},{4,9},{5,10},{6,17},{7,17},{8,20},{9,24},{10,30}};
        for(i=0;i<10;i++){
            array[i].per=array[i].price/array[i].lenght;
        }
    
        //排序 
        for(i=0;i<10-1;i++){
            k=i;
            for(j=1+i;j<10;j++)
            if(array[k].per<array[j].per) k=j;
            if(k!=i) {
                temp=array[i];
                array[i]=array[k];
                array[k]=temp;
            }
        }
    
        printf("请输入将要切割钢条的长度:");
        scanf("%d",&n);
        printf("最优切割方式为：",sum);
        
        for(i=0;i<10;i++){
            if(array[i].lenght<=n){
                m=n/array[i].lenght;
                n=n-m*array[i].lenght;
                //n=n%(int)array[i].lenght;
                sum=sum+m*array[i].price;
                printf("%d个%d  ",m,(int)array[i].lenght);
                }
            if(n==0) break;
        }
    
        printf("\n最高利润为：sum=%d",sum);
        
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTIyNzQy_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190322225717459.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTIyNzQy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTIyNzQy_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20190322225736259.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTIyNzQy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTIyNzQy_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/2019032222574864.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTIyNzQy,size_16,color_FFFFFF,t_70