网站原型的交互怎么做,网站建设哪些职位,佛山市企业网站建设报价,关键词近似装箱问题 解决装箱问题#xff08;bin packing problem#xff09;的算法。也可以用贪婪算法来完成 给定N项物品#xff0c;大小为s1#xff0c;s2#xff0c;s3…sn#xff0c;所有的大小满足0 si 1。问题是要把这些物品装到最小数目的箱子中#xff0c…近似装箱问题 解决装箱问题bin packing problem的算法。也可以用贪婪算法来完成 给定N项物品大小为s1s2s3…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。在一个脱机装箱算法中我们做任何事情都需要等所有的输入数据全被读取之后才进行
联机算法
下项合适算法 算法定义当处理任何一项物品我们检查看他是否能装进去刚才放入物品的箱子中。 如果能那么放入该箱子否则开辟一个新的箱子。 算法实现简单而且还是线性时间下运行 算法实现
/*** 近似装箱问题 - 联机算法 - 脱机算法** 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[][] multiKnasack(int[] source ) {int num source.length;//极端情况所有获取都是1 都在第一个里面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) {if (MAX_WEIGHT - weight[packagePosition] source[i]) {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 multiKnasack(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[][] 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 multiKnasackFirst(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();}}
}首次合适算法时间复杂度达到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();}}
}
上一篇数据结构与算法–贪婪算法 下一篇数据结构与算法–分治算法
