java背包问题

Question

有一个背包的负重最多可达8公斤，而希望在背包中装入负重范围内可得之总价物品，现在有一些物品，单价和重量分别是：黑豆4kg/4500,红豆5kg/5700,黄豆2kg/2250,紫薯1kg/1100,青豆6kg/6700.求装满一背包的物品，背包的价值最大的方案。

代码如下:

class Fruit {

private String name;

private int size;

private int price;

public Fruit(String name, int size, int price) {

this.name = name;

this.size = size;

this.price = price;

}

public String getName() {

return name;

}

public int getPrice() {

return price;

}

public int getSize() {

return size;

}

}

public class KnapsackProblem {

public static void main(String[] args) {

final int MAX = 8;

final int MIN = 1;

int[] item = new int[MAX + 1];

int[] value = new int[MAX + 1];

Fruit fruits[] = { new Fruit("李子", 4, 4500), new Fruit("苹果", 5, 5700),

new Fruit("橘子", 2, 2250), new Fruit("草莓", 1, 1100),

new Fruit("甜瓜", 6, 6700) };

//No.1

//开始写代码，补充完整代码，用动态规划的方法实现背包问题

for (int i = 0 ) {

for (int s = fruits[i].getSize() ) {

int p = s - fruits[i].getSize();

int newvalue = value[p] + fruits[i].getPrice();

}

}

}

//end_code

System.out.println("物品\t价格");

for (int i = MAX; i >= MIN; i = i - fruits[item[i]].getSize()) {

System.out.println(fruits[item[i]].getName() + "\t" + fruits[item[i]].getPrice());

}

System.out.println("合计\t" + value[MAX]);

}

}

Answer 1

设置每种东西的个数为int值，对第一个物品进行循环，最大值为总价/单价取整。 然后在此循环下，对其他的物品进行同样逻辑的循环，保证条件是各个物品的单价*个数相加，不能大于总数。 可以得出不同的结果，获取最大就好。