题解 | #购物单#

看大佬的题解之后使用Java写了压缩空间的方法

包括钱数的压缩和dp数组的一维压缩

public class Main {
    // 状态多一些的01背包问题，每个商品包含价值和权重，分别进行保存
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt() / 10; //总钱数，节省空间
        int m = in.nextInt();// 总物品数目
        int[][] prices = new int[m + 1][3];
        int[][] weights = new int[m + 1][3];
        in.nextLine();
        for (int i = 1; i <= m; i++){
            int v = in.nextInt() / 10;// 需要的钱
            int p = in.nextInt() * v;// 钱*重要度
            int q = in.nextInt();
            in.nextLine();
            if (q == 0){// 主件直接加就行
                prices[i][0] = v;
                weights[i][0] = p;
            }else if (prices[q][1] == 0){// 从件先试着赋值到主件的第一个位置去
                prices[q][1] = v;
                weights[q][1] = p;
            }else{// 1号有从件后赋值到从件2
                prices[q][2] = v;
                weights[q][2] = p;
            }
        }
        int[] dp = new int[N + 1];// 压缩空间到1维
        for (int i = 1; i <= m; i++){// 遍历所有物品
            // 从后向前遍历防止出错，因为这里压缩到了，从前向后的话会将上一行的结果覆盖掉
            for (int j = N; j >= 1; j--){
                //分为四种情况：只放主，放主1+从1，放主2+从2，放主+从1+从2
                int p1 = prices[i][0];// 从件都为0的
                int w1 = weights[i][0];
                int p2 = prices[i][1];
                int w2 = weights[i][1];
                int p3 = prices[i][2];
                int w3 = weights[i][2];
                if (j - p1 >= 0) dp[j] = Math.max(dp[j], dp[j-p1] + w1);
                if (j - p1 - p2 >= 0) dp[j] = Math.max(dp[j], dp[j - p1 - p2] + w1 + w2);
                if (j - p1 - p3 >= 0) dp[j] = Math.max(dp[j], dp[j - p1 - p3] + w1 + w3);
                if (j - p1 -p2 - p3 >= 0) dp[j] = Math.max(dp[j], dp[j - p1 -p2 - p3] + w1 + w2 + w3);
            }
        }
        System.out.println(dp[N] * 10);

    }
}