编辑代码

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



public class Backpack {
     // 装东西的方法
     // 输入：packCapacity：包的容量
     //      items： 可以装的水果
     // 输出：装到的水果集合
     public static LinkedList<Item> containObject(int packCapacity, Item[] items) {
        // 1. 找出子问题，确定表格的行和列
        int rowCount = items.length + 1;
        int colCount = packCapacity + 1;
        // 2. 构建存储子问题的表格
        int[][] dpArray = new int[rowCount][colCount];
        LinkedList<Item> objectContained = new LinkedList<Item>(); // 记录需要装的东西

        //表格清零
        for (int i = 0; i < rowCount; ++i) {
            Arrays.fill(dpArray[i], 0);
        }

        //3. 利用公式（Max(item[i - 1].value + Cell[i-1][j - item[i-1].weight], Cell[i-1][j])）填充动态规划表
        for (int i = 1; i < rowCount; ++i) {
            for (int j = 1; j < colCount; ++j) {
                
                if (items[i-1].weight <= j){
                    // 当前行对应的水果可以放入背包
                    dpArray[i][j] = Math.max(items[i-1].value + dpArray[i - 1][j - items[i-1].weight], dpArray[i-1][j]);
                }
                else {
                    // 当前行对应的水果不可以放入背包
                    dpArray[i][j] = dpArray[i-1][j];
                }
                
            }
        }

        //4. 利用表格找出要放入包中的水果
        int i = rowCount - 1;
        int j = colCount - 1;
        while(i > 0 && j > 0) {

            if (dpArray[i][j] != dpArray[i-1][j]) {
                // 当前行对应的水果被放入包包
                objectContained.addFirst(items[i-1]);
                j = j - items[i-1].weight; // 减去放入包的当前水果的重量
                i = i-1; // 去掉当前水果
            }
            else {
                // 当前行对应的水果不被放入包包
                i = i - 1;// 去掉当前水果
            }
        }

        return objectContained;
    }
	public static void test() {
        Item[] items = {
            new Item("苹果", 300, 15),
            new Item("香蕉", 180, 18),
            new Item("橘子", 150, 10),
            new Item("猕猴桃", 270, 9)
        };

        LinkedList<Item> objectInPack = containObject(20, items);

        int maxValue = 0;

        System.out.println("装了如下水果：");
        for (int i = 0; i < objectInPack.size(); ++i) {
            maxValue += objectInPack.get(i).value;
            System.out.println(objectInPack.get(i).name);
        }

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

	}
    public static void main(String[] args) {
        test();
    }

}

// 定义物品
class Item {
    public String name;
    public int value;
    public int weight;

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