服务器之家

服务器之家 > 正文

c语言来实现贪心算法之装箱问题

时间:2019-12-12 15:09     来源/作者:hebedich

装箱问题,贪心算法求近似最优解

 

复制代码代码如下:

import java.util.Arrays;
import java.util.Comparator;
//装箱问题,贪心算法
public class Enchase {
    public void test1() {
        Integer[] boxs={34,6,40,2,23,12,12};
        int boxCaptation=40;//箱子容量
        //倒序
        Arrays.sort(boxs, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        int unEnchase=boxs.length;//未装箱数
        int minIndex=boxs.length-1;//最小的箱子指向
        while (unEnchase>0) {
            for(int i=0;i<boxs.length;i++){
                //位置箱子重量为零跳过
                if(boxs[i]==0){
                    continue;
                }
                unEnchase--;
                while((boxCaptation-boxs[i])>=boxs[minIndex]){
                    int k=i+1;
                    for(;k>i;k++){
                        //位置箱子重量为零跳过
                        if(boxs[k]==0){
                            continue;
                        }
                        //将箱子加上去,原来位置清零
                        boxs[i]+=boxs[k];
                        int temp=boxs[k];
                        boxs[k]=0;
                        unEnchase--;
                        if(boxs[i]>boxCaptation){
                            //超过最大可容纳体积,状态复原
                            unEnchase++;
                            boxs[k]=temp;
                            boxs[i]-=boxs[k];
                            continue;
                        }
                        //最小箱子更新
                        if(k==minIndex){
                            for(int y=minIndex;y>0;y--){
                                if(boxs[y]!=0){
                                    minIndex=y;
                                }
                            }
                        }
                        break;
                    }
                }
            }
        }
        //统计箱子数
        int Boxcount=0;
        System.out.println("装箱结果:");
        for(int i=0;i<boxs.length;i++){
            System.out.print(boxs[i]+"\t");
            if(boxs[i]==0){
                continue;
            }
            Boxcount++;
        }
        System.out.println("\n箱子数:"+Boxcount);
    }
    public static void main(String[] args) {
        new Enchase().test1();
    }
}

 

以上就是本文的全部内容了,希望大家能够喜欢。

相关文章

热门资讯

玄元剑仙肉身有什么用 玄元剑仙肉身境界等级划分
玄元剑仙肉身有什么用 玄元剑仙肉身境界等级划分 2019-06-21
男生常说24816是什么意思?女生说13579是什么意思?
男生常说24816是什么意思?女生说13579是什么意思? 2019-09-17
配置IIS网站web服务器的安全策略配置解决方案
配置IIS网站web服务器的安全策略配置解决方案 2019-05-23
Nginx服务器究竟是怎么执行PHP项目
Nginx服务器究竟是怎么执行PHP项目 2019-05-24
华为nova5pro和p30pro哪个好 华为nova5pro和华为p30pro对比详情
华为nova5pro和p30pro哪个好 华为nova5pro和华为p30pro对比详情 2019-06-22
返回顶部