题目的链接在代码注释上。解释一下题目思路难点

• 动态规划的思路
• 出题者的变体解决

先学习一下动态规划的核心思路

1. 分割问题到不相关的子问题
2. 通过子问题的最优解逐步推导出全局最优解。

第二步存在公式

$$ df[i][j] = Max(df[i-1][j], v[i] + df[i-1][j-w[i]]) $$

例如 典型的0-1背包和最优路径选择问题

0-1背包问题

一共有m件物品，放进容量为n的背包中。单独对物品而言，一件物品存在两种状态0/1，m件物品的选择一共有2^m种。如果利用最朴素的算法去求解的话，需要把这所有的情况全部计算出来，然后从中选择最优解。这种算法的时间复杂度为log(2ⁿ)，是一种很糟糕的算法，很难应用在实际问题中。

解决这种最优求解问题的思路目前有两种（个人所知）

1. 贪心算法，每次都取当前局部最优解（未必是全局最优解）
2. 动态规划，从最小子问题开始求解，逐步求解到全局最优解（注意NP完全问题不能用此方法求解，可以使用贪心算法求相近值），因为动态规划的算法实现思路趋近于填格子，不断更新当前的优值，因此可以发现这是一种用空间换取时间的算法

变体解决思路

题目中相对于纯粹的动态规划问题增加了附件的设定，这里会使得子问题存在相关性，主件的价值可以存在四种情况 主件-附件1（存在/不存在）-附件2（存在/不存在）。因为需要对附件进行额外的处理，而且上面👆的状态转移公式需要进行一定的修改，这里需要比较主件四种情况在条件限制下的最大价值

$$ df[i][j] = Max(df[i-1][j], v[i][1..4] + df[i-1][j-w[i][1..4]]) $$

题目的解决代码贴在下方👇
（代码实现的写法上还可以继续优化，核心思路相近）

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * 动态规划变体
 * {@link https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4}
 * 购物清单
 */
public class ShopList {
    public static void main(String[] args) {
        try (Scanner scanner = new Scanner(System.in)) {
            int totalMoney = scanner.nextInt();
            int num = scanner.nextInt(); // 物品总数
            /** 物品 第四列放入该物品总满意度 */
            List<wanted> things = new ArrayList<>(num);
            int maxPrice = 0; // 最大价格
            int minPrice = Integer.MAX_VALUE; // 最小价格
            for (int i = 0; i < num; i++) {
                wanted thing = new wanted();
                thing.price = scanner.nextInt(); // price
                thing.importFactory = scanner.nextInt(); // important factory
                thing.depends = scanner.nextInt(); // depends
                if (thing.price < minPrice) {
                    minPrice = thing.price;
                }

                if (thing.price > maxPrice) {
                    maxPrice = thing.price;
                }

                things.add(thing);
            }

            for (wanted thing : things) {
                if (thing.depends != 0) {
                    wanted mainThing = things.get(thing.depends - 1);
                    /* 将附件绑定到主件上 */
                    if (mainThing.f1 == null) {
                        mainThing.f1 = thing;
                    } else {
                        mainThing.f2 = thing;
                    }
                }
            }

            minPrice = 10;
            /** 如果能够整除则表示可以整好根据最小刻度进行均分，如果不能够整除，则最后一个刻度标识最大值 */
            int cols = totalMoney % minPrice == 0 ? totalMoney / minPrice : totalMoney / minPrice + 1;
            int[][] valueMartix = new int[num][cols];

            for (int index = 0; index < num; index++) {
                wanted thing = things.get(index);
                int[][] cAndVals = thing.getValues();

                // 计算每列金额上限的价值最大值
                for (int j = 0; j < cols; j++) {
                    // 当前列的💰上限,处于最后一列时，最大值必须是totalMoney
                    int n = j < cols - 1 ? minPrice * (j + 1) : totalMoney; 
            
                    if (index == 0) {
                        if (thing.depends != 0) {
                            valueMartix[index][j] = 0;
                            continue;
                        }
                        // 金额最少的大于该列金额上限，代表 0行该列无法填入价值
                        if (cAndVals[0][0] > n) {
                            valueMartix[index][j] = 0; // 第一行 无数值
                        } else {
                            valueMartix[index][j] = cAndVals[0][0];
                            for (int[] vals : cAndVals) {
                                if (vals[0] <= n && vals[1] > valueMartix[index][j]) {
                                    valueMartix[index][j] = vals[1];
                                }
                            }
                        }
                    } else {
                        // 附件价值不计算
                        if (thing.depends != 0) {
                            valueMartix[index][j] = valueMartix[index - 1][j];
                            continue;
                        }
                        // 计算主件价值
                        valueMartix[index][j] = valueMartix[index - 1][j];
                        for (int[] vals : thing.getValues()) {
                            // 花费在承受范围内
                            if (vals[0] > 0 && vals[0] <= n) {
                                int d = n - vals[0];
                                // 如果剩余价值不足以再购买，不再计算剩余价值
                                if (d < minPrice) {
                                    // 如果价值大于原先的最高价值，更新
                                    valueMartix[index][j] = Math.max(valueMartix[index][j], vals[1]);
                                } else {
                                    int col = d % minPrice == 0 ? d / minPrice - 1 : Math.floorDiv(d, minPrice);
                                    valueMartix[index][j] = Math.max(vals[1] + valueMartix[index - 1][col],
                                            valueMartix[index][j]);
                                }
                            }
                        }
                    }
                }
            }

            System.out.println(valueMartix[num - 1][cols - 1]);

            for (int[] value : valueMartix) {
                System.out.println("values -> " + Arrays.toString(value));
            }

        }
    }
}

/**
 * 思路，本质上还是动态规划算法，但是附件和和主件不能完全分开，附件有个性质之存在*0-2个*，
 * 
 * 也就是说主件的花费和最大价值的可能性变成 4种 附件1存在/不存在 附件2存在/不存在，这里主件的确认需要确认最小价格～最大价格中取一种
 * （这里面的购买件数无限制，唯一的限制就是价格）
 * 
 * 其他的同一般的动态规划思路，逐步计算每件主件 在不同分段价格下的价值即可，最后获取最大价值
 */

class wanted {
    /**
     * 价格
     */
    int price;

    /**
     * 重要度
     */
    int importFactory;

    /**
     * 依赖的主件
     */
    int depends;

    /**
     * 附件1
     */
    wanted f1;

    /**
     * 附件2
     */
    wanted f2;

    public wanted() {
    }

    /**
     * 计算各个情况的价值和耗费
     * 
     * @return
     */
    public int[][] getValues() {
        int[][] valueList = new int[4][2];
        int value = price * importFactory;
        valueList[0][0] = price;
        valueList[0][1] = value;

        if (this.f1 == null && this.f2 == null) {
            return valueList;
        }

        int c2 = price + (this.f1 == null ? 0 : this.f1.price);
        int value2 = value + (this.f1 == null ? 0 : this.f1.price * this.f1.importFactory);
        valueList[1][0] = c2;
        valueList[1][1] = value2;

        int c3 = price + (this.f2 == null ? 0 : this.f2.price);
        int value3 = value + (this.f2 == null ? 0 : this.f2.price * this.f2.importFactory);
        valueList[2][0] = c3;
        valueList[2][1] = value3;

        int c4 = price + (this.f1 == null ? 0 : this.f1.price) + (this.f2 == null ? 0 : this.f2.price);
        int value4 = value + (this.f1 == null ? 0 : this.f1.price * this.f1.importFactory)
                + (this.f2 == null ? 0 : this.f2.price * this.f2.importFactory);
        valueList[3][0] = c4;
        valueList[3][1] = value4;

        return valueList;
    }
}

Q.E.D.