题解 | 购物单（java版）——动态规划

import java.util.Scanner;

/**
 * @author why
 * @date 2023/04/08 09:40
 * @name
 * @level
 **/
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int money = in.nextInt();
        int num = in.nextInt();

        int[][] dp = new int[num + 1][money / 10 + 1]; //money是10的倍数，这样可以减少空间开支
        Good[] goods = new Good[num + 1]; //物品

        //初始化物品
        for (int i = 1; i <= num; i++) {
            int price = in.nextInt() / 10;
            int weight = in.nextInt();
            int id = in.nextInt();
            goods[i] = new Good(price, weight, id);
        }

        //根据物品的id判断是主件还是附件，如果是附件则更新对应的主件的id1和id2
        for (int i = 1; i <= num; i++) {
            int id = goods[i].id;
            if (id > 0) {
                if (goods[id].id1 == -1) {
                    goods[id].id1 = i; //标识附件存在
                } else {
                    goods[id].id2 = i;
                }
            }
        }

        //开始遍历
        for (int i = 1; i <= num; i++) {
            //分三种情况（这里主+附1和主+附2要分开讨论）
            int money1 = 0, money2 = 0, money3 = 0, money4 = 0; //主，主+附1，主+附2，主+附1+附2
            int value1 = 0, value2 = 0, value3 = 0, value4 = 0; //主，主+附1，主+附2，主+附1+附2

            value1 = goods[i].price * goods[i].weight;
            money1 = goods[i].price;
            if (goods[i].id1 != -1) {
                money2 = goods[goods[i].id1].price + money1;
                value2 = value1 + goods[goods[i].id1].price * goods[goods[i].id1].weight;
            }
            if (goods[i].id2 != -1) {

                money3 = goods[goods[i].id2].price + money1;
                value3 = goods[goods[i].id2].price * goods[goods[i].id2].weight + value1;
            }

            if (goods[i].id1 != -1 && goods[i].id2 != -1) {
                money4 = goods[goods[i].id2].price + money2;
                value4 = goods[goods[i].id2].price * goods[goods[i].id2].weight + value2;
            }
            //System.out.println(value1+" "+value2+" "+value3+" "+value4);

            for (int j = 1; j <= (money / 10); j++) {
                if (goods[i].id > 0) {
                    dp[i][j] = dp[i - 1][j]; //不能单独选中附件
                } else {
                    /*
                    不选择当前物品，因为下面要根据j和money的比较来选择不同的主件和附件的组合情况，所以这里先向上继承，下面当j<money/1/2/3/4
                    //的时候就不用另写分支了
                    详见01背包代码模板：
                    for(int i = 1; i < weight.size(); i++) { // 遍历物品
                        for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
                            if (j < weight[i]) dp[i][j] = dp[i - 1][j];
                            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
                            }
                        }
                    */
                    dp[i][j] = dp[i - 1][j];
                    if (j >= money1) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - money1] + value1); //选中主件
                    }
                    if (j >= money2 && value2 > 0) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - money2] + value2); //选中主件+附件1
                    }
                    if (j >= money3 && value1 > 0) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - money3] + value3); //选中主件+附件2
                    }
                    if (j >= money4 && value4 > 0) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - money4] + value4); //选中主件+附件1+附件2
                    }
                }

            }
        }
        System.out.print(dp[num][money / 10] * 10);
//        for (int i = 1; i <= num; i++) {
//            for (int j = 1; j <= money/10; j++) {
//                System.out.print(dp[i][j] + "  ");
//            }
//            System.out.println();
//        }
    }
}

class Good {
    public int price;
    public int weight;
    public int id;
    public int id1;
    public int id2;

    public Good() {
    }

    ;

    public Good(int p, int w, int i) {
        this.price = p;
        this.weight = w;
        this.id = i;
        this.id1 = -1;
        this.id2 = -1;
    }

}