题解 | #购物单#

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            int money = sc.nextInt();
            int m = sc.nextInt();
            sc.nextLine();
            int[][] prices = new int[m + 1][3];
            int[][] weights = new int[m + 1][3];
            for (int i = 1; i <= m; i++) {
                int a = sc.nextInt();
                int b = sc.nextInt();
                int c = sc.nextInt();
                b = b * a;//weight
                if (c == 0) {
                    // 主件
                    prices[i][0] = a;
                    weights[i][0] = b;
                } else if (prices[c][1] == 0) {
                    // 附件1
                    prices[c][1] = a;
                    weights[c][1] = b;
                } else {
                    // 附件2
                    prices[c][2] = a;
                    weights[c][2] = b;
                }
                sc.nextLine();
            }
            int[][] dp = new int[m + 1][money + 1];
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= money; j++) {
                    int a = prices[i][0];
                    int b = weights[i][0];
                    int c = prices[i][1];
                    int d = weights[i][1];
                    int e = prices[i][2];
                    int f = weights[i][2];

                    dp[i][j] = j - a >= 0 ? Math.max(dp[i - 1][j],
                                                     dp[i - 1][j - a] + b) : dp[i - 1][j];
                    dp[i][j] = j - a - c >= 0 ? Math.max(dp[i][j],
                                                         dp[i - 1][j - a - c] + b + d) : dp[i][j];
                    dp[i][j] = j - a - e >= 0 ? Math.max(dp[i][j],
                                                         dp[i - 1][j - a - e] + b + f) : dp[i][j];
                    dp[i][j] = j - a - c - e >= 0 ? Math.max(dp[i][j],
                               dp[i - 1][j - a - c - e] + b + d + f) : dp[i][j];
                }
            }
            System.out.println(dp[m][money]);
        }
    }
}

怕自己忘了思路，记录一下(代码参考牛客网上的已有代码，思路参考的是哔哩哔哩上的教学视频)：

这是一个使用动态规划解决背包问题的Java代码，主要用于处理购物问题，其中物品可以有主件和附件。以下是对代码的分析：

1. 输入处理：通过Scanner从标准输入读取数据，首先读取总预算money和商品数量m。使用二维数组prices和weights分别存储物品的价格和重量。这里设置了3列，分别表示主件、附件1和附件2。
2. 动态规划：使用二维数组dp进行动态规划，其中dp[i][j]表示前i个物品在预算为j时的最大总重量。通过两层循环遍历所有物品和预算的组合，计算最大总重量。对于每个物品，分别考虑选择主件、附件1、附件2或同时选择附件1和附件2的情况，更新dp[i][j]的值。

总体来说，这段代码通过动态规划的方式解决了购物问题，其中商品可以有主件和附件，附件的选择可能影响到其他物品。

补充：

在某些情况下，nextInt() 等方法可能不会读取整行的内容，而只会读取到当前行的有效部分。为了确保在接下来的循环迭代中从下一行开始读取，使用 nextLine() 来移动到下一行是一个常见的做法。