题解 | #购物单#

import java.util.*;
//动态规划 01背包问题 时间复杂度O[n*m]，空间复杂度O[n]
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        //一.数据录入及格式转换
        int n = in.nextInt();//总钱数
        int m = in.nextInt();//物品总数
        Goods[] list = new Goods[m];
        //初始化，避免赋值空指针
        for (int i = 0; i < m; i++) {
            list[i] = new Goods();
        }
        //录入并初始化物品数据list，将附件放入主件属性中
        for (int i = 0; i < m; i++) {
            int price = in.nextInt(); //价格
            int important = in.nextInt(); //重要度
            int mainNo = in.nextInt(); //0为主，否则为所属主件编号

            list[i].price = price; //价格
            list[i].weight = price * important; //满意度

            if (mainNo == 0) {
                list[i].isMain = true;
            } else {
                Goods parent = list[mainNo - 1];
                if (parent.fj1 == null) {
                    parent.fj1 = list[i];
                } else {
                    parent.fj2 = list[i];
                }
            }
        }
        //二、动态规划:
        /**
        dp[i][j]=Max(
            dp[i-1][j],
            dp[i-1][j-v[i]]+w[i],
            dp[i-1][j-v[i]-vfj1[i]]+w[i]+wfj1[i],
            dp[i-1][j-v[i]-vfj2[i]]+w[i]+wfj2[i],
            dp[i-1][j-v[i]-vfj1[i]-vfj2[i]]+w[i]+wfj1[i]+wfj2[i]
            )
         */
        int[] dp = new int[n + 1];
        for (int i = 0; i < m; i++) {
            Goods goods = list[i];
            for (int j = n ; j >= 0; j--) {
                if (!goods.isMain) { //不是主件直接忽略
                    continue;
                }
                int w1 = 0, w2 = 0, w3 = 0, w4 = 0, w5 = 0;
                int max = 0;
                //1.不购买物品i
                max = w1 = dp[j];
                //2.购买物品i
                if (j >= goods.price) {
                    w2 = dp[j - goods.price] + goods.weight;
                    max = Math.max(max, w2);
                }
                //3.购买物品i和附件1
                if (goods.fj1 != null && j >= (goods.price + goods.fj1.price)) {
                    w3 = dp[j - goods.price - goods.fj1.price] + goods.weight + goods.fj1.weight;
                    max = Math.max(max, w3);
                }
                //4.购买物品i和附件2
                if (goods.fj2 != null && j >= (goods.price + goods.fj2.price)) {
                    w4 = dp[j - goods.price - goods.fj2.price] + goods.weight + goods.fj2.weight;
                    max = Math.max(max, w4);
                }
                //5.购买物品i和附件1和附件2
                if (goods.fj1 != null && goods.fj2 != null &&
                        j >= (goods.price + goods.fj1.price + goods.fj2.price)) {
                    w5 = dp[j - goods.price - goods.fj1.price - goods.fj2.price] + goods.weight +
                         goods.fj1.weight + goods.fj2.weight;
                    max = Math.max(max, w5);
                }
                //6.取最大值
                dp[j] = max;
            }
        }

        //三、输出结果
        System.out.print(dp[n]);
    }
}
class Goods {
    int price;//价格
    int weight;//满意度
    boolean isMain;//是否主件
    Goods fj1;//附件1
    Goods fj2;//附件2
}