背包问题

package 二〇一七年三月二十四日; import java.util.Arrays; public class 背包问题 { public static void main(String args[]) { double M = 10; // 定义背包容量为10 Goods[] g = new Goods[10]; // 定义10个物品 g[0] = new Goods(2, 1.4); // Goods(容量, 价值) g[1] = new Goods(1.2, 5); g[2] = new Goods(2.1, 3); g[3] = new Goods(2.4, 4); g[4] = new Goods(1.8, 1.4); g[5] = new Goods(2.2, 6); g[6] = new Goods(1.1, 1); g[7] = new Goods(1.5, 3); g[8] = new Goods(1.1, 0.9); g[9] = new Goods(2, 2); System.out.println("物体未排序前的价值容量比(value/volume)："); for (Goods e : g) { System.out.printf("%-8.1f", e.value / e.volume); } System.out.println(); System.out.println("物体排序后的价值容量比(value/volume)："); Arrays.sort(g); for (Goods e : g) { System.out.printf("%-8.1f", e.value / e.volume); } System.out.println(); double[] x = new double[10]; // 存储每个物品放入背包的程度，0<=x<=1 int i = 0; while (M != 0 && i < g.length) { if (g[i].volume <= M) { x[i] = 1; M -= g[i].volume; ++i; } else { x[i] = M / g[i].volume; M = 0; } } System.out.println("贪心策略解决背包放入物品问题："); for (i = 0; i < 10; ++i) System.out.printf("#%d:%-5.1f \n", i, x[i]); System.out.println(); } } class Goods implements Comparable<Goods> { public double volume = 0; public double value = 0; public Goods(double vol, double val) { volume = vol; value = val; } public int compareTo(Goods other) { if (value / volume < other.value / other.volume) return 1; if (value / volume > other.value / other.volume) return -1; return 0; } }