装箱问题，贪心算法求近似最优解
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();
}
}
以上就是本文的全部内容了，希望大家能够喜欢。
如对本文有疑问，
点击进行留言回复！！
我要评论
网友评论