贪⼼算法最优装载问题（Java代码实现）最优装载问题
最优装载问题实质上就是⼀个简单版的0-1背包问题
问题描述
有⼀批集装箱要装上⼀艘载重量为 c 的轮船，其中集装箱 i 的重量为 w
i
最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船
算法描述
可⽤贪⼼算法求解
采⽤重量最轻者先装的贪⼼选择策略，可产⽣最优装载问题的最优解
Java 源代码
代码有详细注释，不懂评论下⽅留⾔
/
*
* 若尘
*/
package loading;
import java.util.Arrays;
/**
* 最优装载问题（贪⼼算法）
* @author ruochen
* @version 1.0
*/
public class LoadingProblem {
private static int[] x;
/**
*
* @param c 总重量
* @param w 每个集装箱的重量
* @param x 记录是否装⼊（1：装⼊    0：不装⼊）
java源代码加密* @return
*/
public static float Loading(float c,float[] w,int[] x){
int n = w.length;
Element[] d =new Element[n];
for(int i =0; i < n; i++){
// 初始化
d[i]=new Element(w[i], i);
}
Arrays.sort(d);
// 记录最优值
float opt =0;
for(int i =0; i < n; i++){
// 初始化
x[i]=0;
}
for(int i =0; i < n && d[i].w <= c; i++){
x[d[i].i]=1;
opt += d[i].w;
c -= d[i].w;
}
}
return opt;
}
public static void main(String[] args){
float c =10;
float[] w =new float[]{4,2,5,1,3};
x =new int[w.length];
float opt =Loading(c, w, x);
System.out.println("最优值为: "+ opt);
System.out.println("最优解为： "+ String(x));
}
public static class Element implements Comparable<Element>{ float w;
int i;
public Element(float w,int i){
this.w = w;
this.i = i;
}
/
**
* 按照升序排列
*/
@Override
public int compareTo(Element o){
if(this.w < o.w)
return-1;
else if(this.w == o.w)
return0;
else
return1;
}
}
}
最优值为: 10.0
最优解为： [1, 1, 0, 1, 1]