public class Backpack {
    // 定义物品的静态内部类
    static class Item {
        String name;
        int weight;
        int value;
        Item(String name, int weight, int value) {
            this.name = name;
            this.weight = weight;
            this.value = value;
        }
    }
    // 动态规划解决背包问题的方法
    static int backpack(Item[] items, int len, int packCapacity) {
        int[][] dp = new int[len + 1][packCapacity + 1];
        // 初始化数组
        for (int i = 0; i <= len; ++i) {
            for (int j = 0; j <= packCapacity; ++j) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = -1;  //表示未计算过
                }
            }
        }
        // 填充动态规划数组
        for (int i = 1; i <= len; ++i) {
            for (int j = 1; j <= packCapacity; ++j) {
                if (items[i - 1].weight <= j) {
                    // 当前物品可以放入背包，选择放或不放的最优值
                    dp[i][j] = Math.max(dp[i - 1][j], items[i - 1].value + dp[i - 1][j - items[i - 1].weight]);
                } else {
                    // 当前物品放不进背包，继承前一个状态
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[len][packCapacity];
    }

    public static void main(String[] args) {
        // 示例物品
        Item[] items = {new Item("吉他",1,1500),new Item("音响",4,3000),new Item("电脑",3,2000),new Item("手机",1,2000)};
        // 物品数量
        int itemCount = items.length;
        // 背包容量
        int packCapacity = 4;
        // 计算最优值
        int result = backpack(items, itemCount, packCapacity);
        // 输出结果
        System.out.println("20052266 杨煜聪");
        System.out.println("最大的结果是：" + result);
    }
}