编辑代码

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;

class Backpack {
public static void stealObjects(int packCapacity, Item[] items, int curItemIndex, int[] path, LinkedList<Item> objectsStolen) {

if (curItemIndex == items.length) {
objectsStolen.clear();
for (int index = 0; index < path.length; ++index) {
if (path[index] > 0) {
objectsStolen.add(items[index]);
}
}
return;
}

// 当前的最佳解
int maxValue = 0;
for (int i = 0; i < objectsStolen.size(); ++i) {
maxValue += objectsStolen.get(i).value;
}

//当前已选的价值和重量
int curValue = 0;
int curWeight = 0;
for (int i = 0; i < curItemIndex; ++i) {
if (path[i] > 0) {
curValue += items[i].value;
curWeight += items[i].weight;
}
}

//放入当前物体
//保证物体是能够放入，方案是可行的
if (items[curItemIndex].weight <= packCapacity - curWeight) {

path[curItemIndex] = 1;

//当前节点的边界值
int upperValue = 0;
upperValue = curValue + items[curItemIndex].value;
if (curItemIndex < items.length - 1) {
Item nextItem = items[curItemIndex + 1];
upperValue += (packCapacity - curWeight - items[curItemIndex].weight) * (nextItem.value/nextItem.weight);
}

//边界值能超越当前最佳解
if (upperValue > maxValue) {
stealObjects(packCapacity, items, curItemIndex + 1, path, objectsStolen);
}

}

//不放入当前物体
path[curItemIndex] = 0;

//当前最佳解
maxValue = 0;
for (int i = 0; i < objectsStolen.size(); ++i) {
maxValue += objectsStolen.get(i).value;
}

//当前节点的边界值
int upperValue = curValue;
if (curItemIndex < items.length - 1) {
Item nextItem = items[curItemIndex + 1];
upperValue += (packCapacity - curWeight) * (nextItem.value/nextItem.weight);
}

//边界值能超越当前最佳解
if (upperValue > maxValue) {
stealObjects(packCapacity, items, curItemIndex + 1, path, objectsStolen);
}

}

public static LinkedList<Item> solveBackpackProblem(int packCapacity, Item[] items) {
LinkedList<Item> objectsStolen = new LinkedList<Item>();
int[] path = new int[items.length];

//按照单价从高到低进行排序
Arrays.sort(items, new Comparator<Item>() {
public int compare(Item left, Item right) {
double leftUnitPrice =(double) left.value/left.weight;
double rightUnitPrice =(double) right.value/right.weight;
if (leftUnitPrice > rightUnitPrice){
return -1;
}
else if (leftUnitPrice == rightUnitPrice) {
return 0;
}
else {
return 1;
}
}
});

stealObjects(packCapacity, items, 0, path, objectsStolen);
return objectsStolen;
}

public static void main(String[] args) {
Item[] items = {
new Item("IPhone", 2000, 1),
new Item("吉他", 1500, 1),
new Item("笔记本电脑", 2000, 3),
new Item("音箱", 3000, 4)
};

int[] path = {0, 0, 0, 0};

int maxValue = 0;
LinkedList<Item> objectsStolen = solveBackpackProblem(4, items);


System.out.println("偷了如下物品：");
for (Item item : objectsStolen) {
maxValue += item.value;
System.out.println(item.name);
}

System.out.println("总价值：" + maxValue);

}
}
class GreedyItem {
public String name;
public double totalWeight;
public double totalValue;

public GreedyItem(String itemName, double weight, double value) {
this.name = itemName;
this.totalWeight = weight;
this.totalValue = value;
}

public GreedyItem(GreedyItem item) {
this.name = item.name;
this.totalWeight = item.totalWeight;
this.totalValue = item.totalValue;
}
}

class Item {
public String name;
public int value;
public int weight;

public Item(String n, int v, int w) {
this.name = n;
this.value = v;
this.weight = w;
}
}