数据结构与算法--贪婪算法2

短命女 2023-01-07 05:57 148阅读 0赞

#### 近似装箱问题 ####

*  解决装箱问题（bin packing problem）的算法。也可以用贪婪算法来完成
 *  给定N项物品，大小为s1，s2，s3…sn，所有的大小满足0 < si < 1。问题是要把这些物品装到最小数目的箱子中，已知每一个箱子容量是1个单位。我们用如下案例，有大小如下的物品：0.2, 0.5, 0.4, 0.7, 0.1, 0.3, 0.8的一列物品最优装修办法
 *  有两种结局方案：
    
     *  一种联机装箱问题（online bin packing problem）。在这种问题中，每一件物品必须放入一个箱子之后才能处理下一个物品
     *  第二中脱机装箱问题（offline bin packing problem）。在一个脱机装箱算法中，我们做任何事情都需要等所有的输入数据全被读取之后才进行

##### 联机算法 #####

###### 下项合适算法 ######

*  算法定义：当处理任何一项物品，我们检查看他是否能装进去刚才放入物品的箱子中。 如果能，那么放入该箱子，否则，开辟一个新的箱子。
 *  算法实现简单，而且还是线性时间下运行
 *  算法实现：

*  下项合适算法有一个合理的性能保证，但是效果在实践中很差，因为在不需要开普新箱子的时候他却会开辟一个新的箱子。

###### 首次合适算法 ######

*  算法定义：有序扫描箱子，并把新的物品放入足够能放下他的第一个箱子中。因此只有当前面那些放置物品的箱子已经容纳不下当前物品的时候才会开辟新的箱子
 *  算法实现：

*  首次合适算法时间复杂度达到O(N^2)，

###### 最佳适合算法 ######

*  第三种策略最佳适合装箱法。改算法不是把一项物品放入所发现的第一个能容纳他的箱子，而是放到所有箱子中能容纳他的最满的哪一个箱子中。典型的方法。
 *  算法实现：

package com.ljm.resource.math.greedy;
    
    import java.util.Random;
    
    /** * 近似装箱问题 - 联机算法 - 脱机算法 * * @author liaojiamin * @Date:Created in 14:12 2021/1/15 */
    public class KnapsackProblem { 
    
        private static final int MAX_WEIGHT = 10;
    
        /** * 随机生成10 以内的物品数据 */
        public static int[] getSource(int num) { 
            int[] source = new int[num];
            Random random = new Random();
            for (int i = 0; i < num; i++) { 
                source[i] = random.nextInt(10);
                System.out.println(source[i]);
            }
            return source;
        }
    
        /** * 最佳合适算法 * 将物品放入一个能容纳他并且最满的箱子中 * */
        public static int[][] multiKnasackBest(int[] source ){ 
            int num = source.length;
            int[][] myPackage = new int[num][num];
            int[] position = new int[num];
            int[] weight = new int[num];
            int packagePosition = 0;
            for (int i = 0; i < source.length; i++) { 
                int maxWeight = -1;
                int maxWeightId = -1;
                for (int j = 0; j <= packagePosition; j++) { 
                    if(MAX_WEIGHT - weight[j] > source[i]){ 
                        if(weight[j] > maxWeight){ 
                            maxWeight = weight[j];
                            maxWeightId = j;
                        }
                    }
                }
                if(maxWeightId < 0){ 
                    packagePosition++;
                    myPackage[packagePosition][position[packagePosition]] = source[i];
                    weight[packagePosition] += source[i];
                    position[packagePosition] += 1;
                }else { 
                    myPackage[maxWeightId][position[maxWeightId]] = source[i];
                    weight[maxWeightId] += source[i];
                    position[maxWeightId] += 1;
                }
            }
            return myPackage;
        }
    
        
    
        public static void main(String[] args) { 
            int[] source = getSource(20);
            int[][] myPackage = multiKnasackBest(source);
            for (int i = 0; i < myPackage.length; i++) { 
                System.out.print("第" + i + "个箱子：");
                for (int i1 = 0; i1 < myPackage[i].length; i1++) { 
                    if (myPackage[i][i1] > 0) { 
                        System.out.print(myPackage[i][i1] + ", ");
                    }
                }
                System.out.println();
            }
        }
    }

##### 脱机算法 #####

*  如果我们能够观察全部物品在给出答案，那么我们应该会做的更好。实时确实如此，我们通过彻底的搜索总能找到最优的装箱方法，因此我们对联机的情况下进行改进
 *  我们联机算法中，主要问题在于大项物品装箱困难，特别是当他们输入的后期出现的时候，总要新建立一个箱子。我们脱机算法中先将物品按照权重排序，这样大的在前面。次数我们应用首次适合算法，或者最佳适合算法得到解决，他们分别是**首次适合递减算法**，**最佳适合递减算法**
 *  首次适合递减算法算法实现：

/** * 近似装箱问题 - 联机算法 - 脱机算法 * * @author liaojiamin * @Date:Created in 14:12 2021/1/15 */
    public class KnapsackProblem { 
    
        private static final int MAX_WEIGHT = 10;
    
        /** * 随机生成10 以内的物品数据 */
        public static int[] getSource(int num) { 
            int[] source = new int[num];
            Random random = new Random();
            for (int i = 0; i < num; i++) { 
                source[i] = random.nextInt(10);
                System.out.println(source[i]);
            }
            return source;
        }
    
      
        public static int[][] multiknasackDecreasing(int[] source){ 
            quickSort(source, 0, source.length - 1);
            return multiKnasackFirst(source);
        }
    
        /** * 快排从大到小 * */
        public static void quickSort(int[] source, int left, int right){ 
            if(left > right){ 
                int temp = swap(source, left, right);
                quickSort(source, left, temp - 1);
                quickSort(source, temp + 1, right);
            }
        }
    
        public static int swap(int[] source, int left, int right){ 
            if (left < right){ 
                int position = source[left];
                while (left < right){ 
    
                    while(left < right && position > source[right]){ 
                        right --;
                    }
                    if(left < right){ 
                        source[right] = source[left];
                        left ++;
                    }
                    while (left < right && position < source[left]){ 
                        left ++;
                    }
                    if(left < right){ 
                        source[left] = source[right];
                        right --;
                    }
                }
                source[left] = position;
            }
            return left;
        }
    
    
    
    
        /** * 首次适合算法： * 义序草庙箱子，并把新的一项物品放入能容纳的箱子中 * */
        public static int[][] multiKnasackFirst(int[] source ){ 
            int num = source.length;
            int[][] myPackage = new int[num][num];
            int[] position = new int[num];
            int[] weight = new int[num];
            int packagePosition = 0;
            for (int i = 0; i < source.length; i++) { 
                boolean isInsert = false;
                for (int j = 0; j < weight.length; j++) { 
                    if(MAX_WEIGHT - weight[j] >= source[i]){ 
                        isInsert = true;
                        myPackage[j][position[j]] = source[i];
                        weight[j] += source[i];
                        position[j] += 1;
                        break;
                    }
                }
                if(!isInsert){ 
                    packagePosition ++;
                    myPackage[packagePosition][position[packagePosition]] = source[i];
                    weight[packagePosition] += source[i];
                    position[packagePosition] += 1;
                }
            }
            return myPackage;
        }
    
        
        public static void main(String[] args) { 
            int[] source = getSource(20);
            int[][] myPackage = multiknasackDecreasing(source);
            for (int i = 0; i < myPackage.length; i++) { 
                System.out.print("第" + i + "个箱子：");
                for (int i1 = 0; i1 < myPackage[i].length; i1++) { 
                    if (myPackage[i][i1] > 0) { 
                        System.out.print(myPackage[i][i1] + ", ");
                    }
                }
                System.out.println();
            }
        }
    }

[上一篇：数据结构与算法–贪婪算法][Link 1]  
[下一篇：数据结构与算法–分治算法][Link 2]

[Link 1]: https://blog.csdn.net/liaojiamin0102/article/details/112573784
[Link 2]: https://blog.csdn.net/liaojiamin0102/article/details/113392976