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值，对第一个物品进行循环，最大值为总价/单价取整。 然后在此循环下，对其他的物品进行同样逻辑的循环，保证条件是各个物品的单价*个数相加，不能大于总数。 可以得出不同的结果，获取最大就好。