部分背包 贪心算法

部分背包：

由于部分背包较容易实现，就将具体数据放于测试类中。 编写处理函数，最好由main调用，得出结果。 1，背包属性等值如0-1背包。

2，由于是贪心算法，首先对背包按照背包的单位价值进行排序

3，按照顺序获取背包的值，累加到总价值上，在不超过背包总重量的情况下，尽可能往里多装价值

具体代码如下：

public class tanxin {

public static class Thing { //物品类 int weight; //重量 int value; //价值

int rate; //重量价值 = 价值/重量 boolean isfilled; //是否装进了背包 public Thing(){}

public Thing(int weight, int value) { this.weight = weight; this.value = value; rate = value / weight; } }

public static void main(String args[]) { Thing[] t = new Thing[3]; t[0] = new Thing(30, 180); t[1] = new Thing(20, 140); t[2] = new Thing(40, 200); int i, j; Thing temp;

for (i = 0; i <= 2; i++) //按rate值由高到低排序 {

for (j = i + 1; j <= 2; j++) {

if(t[i].rate < t[j].rate) {

temp = t[i]; t[i] = t[j]; t[j] = temp; } } }

System.out.print(\"重量价值排序：\"); for(i=0;i<=2;i++)

System.out.print(t[i].rate+\); 运

行

出

来

的

结

果

如

下

：