购物单

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 总钱数
        int n = scanner.nextInt();
        // 购买物品个数
        int m = scanner.nextInt();

        // 分组，goods[i]
        Good[] goodList = new Good[m + 1];

        //所有商品赋值
        for (int i = 1; i <= m; i++) {
            int v = scanner.nextInt();
            int w = scanner.nextInt();
            int q = scanner.nextInt();
            goodList[i] = new Good(v, w, q);
            //是否为主件
            goodList[i].isMain = q == 0;
        }

        //遍历附件商品，赋给主件Good
        for (Good good1 : goodList) {
            if (good1 == null) {
                continue;
            }
            if (good1.isMain) {continue;}
            if (goodList[good1.q].subGood1 == null) {
                goodList[good1.q].subGood1 = good1;
            } else {
                goodList[good1.q].subGood2 = good1;
            }
        }

        //初始化动态规划数组 用以保存每个总价能得到的最大重要度
        int[] dp = new int[n+1];
        //再次遍历开始计算
        for (Good good : goodList) {
            if (good == null) {
                continue;
            }
            //附件直接跳过
            if (!good.isMain) {continue;}

            //考虑所有组合可能性，分为四类：只要主件 主件+附件1 主件+附件2 主件+附件1+附件2
            int v = good.v;
            int ***bsp;= good.v * good.p;

            int[][] cases = new int[4][2];

            //只要主件
            cases[0] = new int[]{v,***bsp;           //主件+附件1
            if (good.subGood1 != null) {
                cases[1] = new int[]{v+good.subGood1.v,***bsp;+ (good.subGood1.v * good.subGood1.p)};
            }

            if (good.subGood2 != null) {
                //主件+附件2
                cases[2] = new int[]{v+good.subGood2.v,***bsp;+ (good.subGood2.v * good.subGood2.p)};
                //主件+附件1+附件2
                cases[3] = new int[]{v+good.subGood1.v+good.subGood2.v,***bsp;+ (good.subGood1.v * good.subGood1.p) + (good.subGood2.v * good.subGood2.p)};
            }

            //开始动态数组更新
            for (int j = n; j >= 0; j--) {
                for (int[] item : cases) {
                    int cost = item[0];
                    int value = item[1];
                    if (cost > 0 && j >= cost) {
                        dp[j] = Math.max(dp[j], dp[j - cost] + value);
                    }
                }
            }
        }
        System.out.println(dp[n]);
    }
}

class Good {
    int v; //价格
    int p; //重要度
    int q; //主件编号
    boolean isMain;
    Good  subGood1;
    Good  subGood2;
    public Good(int v, int p, int q) {
        this.v = v;
        this.p = p;
        this.q = q;
    }
}

import java.util.LinkedList;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    static class Product{
        public int v; //价格
        public int w; //重要程度
        public int q; //主件编号

        public Product(int a,int b,int c){
            v=a;w=b;q=c;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int budget = scanner.nextInt(); //预算
        int num = scanner.nextInt(); //商品数目
        LinkedList<Product>[] list = new LinkedList[num]; //附件列表
        for (int i = 0; i < num; i++) {
            list[i] = new LinkedList<>();
        }

        Product[] products = new Product[num];
        int[] dp = new int[budget+1]; //dp[i]代表的是i的预算去购买最大的满意度

        for (int i = 0; i < num; i++) {
            int v = scanner.nextInt();
            int w = scanner.nextInt();
            int q = scanner.nextInt();
            products[i] = new Product(v,w,q);

            if(q!=0){
                list[q-1].add(products[i]);
            }
        }

        //当前可购买的列表只有0-i个商品
        for(int i=0;i<num;i++){ //一件一件增加商品类别
            //只考虑主件，附件是主件自带的
            if(products[i].q>0)
                continue;
            for (int j = budget; j >=0 ; j-- ) { //从后往前，可以防止重复购买i件商品
                if(j>=products[i].v) //当前的钱可以购买第j件产品
                {   // 选择购买当前第i件产品和不购买的满意度取max
                    dp[j] = Math.max(dp[j],dp[j-products[i].v]+products[i].v*products[i].w);
                }
                //主件+附件
                if(list[i].size()>0&&j>=products[i].v+list[i].getFirst().v){
                    dp[j] = Math.max(dp[j],
                            dp[j-products[i].v-list[i].getFirst().v]  + products[i].v*products[i].w + list[i].getFirst().v*list[i].getFirst().w);
                }
                if(list[i].size()>1&&j>=products[i].v+list[i].get(1).v){ //有两件附件
                    dp[j] = Math.max(dp[j],dp[j-products[i].v-list[i].get(1).v]+products[i].v*products[i].w+list[i].get(1).v*list[i].get(1).w);
                }
                if(list[i].size()>1&&j>=products[i].v+list[i].getFirst().v+list[i].get(1).v){
                    dp[j] = Math.max(dp[j],dp[j-products[i].v-list[i].getFirst().v-list[i].get(1).v]+products[i].v*products[i].w+list[i].get(1).v*list[i].get(1).w+list[i].getFirst().v*list[i].getFirst().w);
                }
                if(i==num-1)
                    break; //最后一件产品不需要计算前面的数值
            }
        }
        System.out.println(dp[budget]);

    }

}

这是一个典型的0-1 背包问题的变种，其中存在主件和附件的约束关系。我们需要使用动态规划来解决这个问题。

问题分析

1. 主件和附件的关系：

   • 物品可以是主件（q = 0）或附件（q > 0）。
   • 如果物品是附件，则必须购买其所属的主件才能购买该附件。

2. 目标：

   • 在不超过预算N的前提下，选择购买物品使得总满意度（价格乘以重要度的和）最大。

3. 思路：

   • 将每个主件和它的附件组合视为一个整体，考虑如何购买这些组合来获得最大满意度。
   • 使用动态规划来解决这个多重背包问题。

   • package com.shisui.medium;
     import java.util.*;
     public class shopping_list {
     
         public static void main(String[] args) {
             Scanner sc = new Scanner(System.in);
             int N = sc.nextInt(); // 总钱数
             int m = sc.nextInt(); // 物品个数
             int[] dp = new int[N + 1]; // dp数组，dp[j]表示总价不超过j时的最大满意度
     
             // 物品信息
             Item[] items = new Item[m + 1];
             List<Item>[] attachments = new List[m + 1];
     
             // 初始化
             for (int i = 0; i <= m; i++) {
                 attachments[i] = new ArrayList<>();
             }
     
             // 读取物品数据
             for (int i = 1; i <= m; i++) {
                 int v = sc.nextInt();
                 int p = sc.nextInt();
                 int q = sc.nextInt();
                 items[i] = new Item(v, p, q);
                 if (q > 0) {
                     attachments[q].add(items[i]); // 把附件添加到对应的主件附件列表中
                 }
             }
     
             // 动态规划求解
             for (int i = 1; i <= m; i++) {
                 if (items[i].q > 0) continue; // 处理附件时跳过
                 for (int j = N; j >= 0; j--) { // 从总钱数开始倒序遍历
                     // 主件选项
                     if (j >= items[i].v) {
                         dp[j] = Math.max(dp[j], dp[j - items[i].v] + items[i].v * items[i].p);
                     }
                     // 主件+附件1选项
                     if (attachments[i].size() >= 1 && j >= items[i].v + attachments[i].get(0).v) {
                         dp[j] = Math.max(dp[j], dp[j - items[i].v - attachments[i].get(0).v]
                                 + items[i].v * items[i].p
                                 + attachments[i].get(0).v * attachments[i].get(0).p);
                     }
                     // 主件+附件2选项
                     if (attachments[i].size() == 2 && j >= items[i].v + attachments[i].get(1).v) {
                         dp[j] = Math.max(dp[j], dp[j - items[i].v - attachments[i].get(1).v]
                                 + items[i].v * items[i].p
                                 + attachments[i].get(1).v * attachments[i].get(1).p);
                     }
                     // 主件+附件1+附件2选项
                     if (attachments[i].size() == 2 && j >= items[i].v + attachments[i].get(0).v + attachments[i].get(1).v) {
                         dp[j] = Math.max(dp[j], dp[j - items[i].v - attachments[i].get(0).v - attachments[i].get(1).v]
                                 + items[i].v * items[i].p
                                 + attachments[i].get(0).v * attachments[i].get(0).p
                                 + attachments[i].get(1).v * attachments[i].get(1).p);
                     }
                 }
             }
             System.out.println(dp[N]);
         }
     
         // 定义一个Item类来存储物品信息
         static class Item {
             int v; // 价格
             int p; // 重要度
             int q; // 0表示主件，其他表示附件所属主件的编号
     
             public Item(int v, int p, int q) {
                 this.v = v;
                 this.p = p;
                 this.q = q;
             }
         }
         }
     
     

     
     
     

个人也是第一次接触算法这个领域，本身只是个搬砖的，如果解法有不好的地方，欢迎各位指出。

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

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int limitMoney = in.nextInt();
            int n = in.nextInt();
            List<Goods> goodsList = new ArrayList<Goods>();
            for (int i = 0; i < n; i++) {
                int price = in.nextInt();
                int value = in.nextInt() * price;
                int type = in.nextInt();
                Goods goods = new Goods(i + 1, price, value, type);
                goodsList.add(goods);
            }
            ShoppingPlan shoppingPlan = calculateMaxValue(goodsList, limitMoney);
            System.out.println(shoppingPlan.getTotalValue());
        }
    }

    public static ShoppingPlan calculateMaxValue(List<Goods> goodsList,
            int limitMoney) {
        // 最大公约数
        int gcd = getArrayGcd(goodsList);
        int n = goodsList.size();
        int m = limitMoney / gcd;
        ShoppingPlan[][] dp = new ShoppingPlan[n + 1][m + 1];
        // 初始化边界
        dp[0][0] = new ShoppingPlan();
        for (int i = 1; i <= n; i++) {
            dp[i][0] = dp[0][0];
        }
        for (int j = 1; j <= m; j++) {
            dp[0][j] = dp[0][0];
        }
        // 计算动态规划矩阵
        for (int i = 1; i <= n; i++) {
            Goods goods = goodsList.get(i - 1);
            for (int j = 1; j <= m; j++) {
                // 构建新的购物方案
                ShoppingPlan plan = new ShoppingPlan();
                // 基础方案的索引值
                int planIndex = j - goods.getPrice() / gcd;
                // 是否附件
                if (goods.isAttachment()) {
                    // 索引之需大于等于0，购买的钱才是足够的
                    if (planIndex >= 0) {
                        // 获取主件
                        Goods mainGoods = goodsList.get(goods.getType() - 1);
                        // 判断选取的基础方案是否有主件，决定是否添加主件
                        boolean hasMainGoods = dp[i - 1][planIndex].hasMainGoods(goods);
                        if (!hasMainGoods) {
                            // 如果选取的基础方案没有购买主件，则需要腾出购买主件的钱，需要将基础方案再往前推
                            planIndex -= mainGoods.getPrice() / gcd;
                        }
                        // 腾出钱之后，看看够不够买，如果不够，那就不使用基础方案了，使用新方案从头开始
                        if (planIndex >= 0) {
                            // 前如果够那就复制一份基础方案
                            plan = dp[i - 1][planIndex].createSnapshot();
                        }
                        // 然后再加上买主件
                        if (!hasMainGoods) {
                            plan.addGoods(mainGoods);
                        }
                    }
                } else {
                    // 主件处理
                    if (planIndex >= 0) {
                        // 只需要判断钱够不够就行了，方案的索引大于0，就是够钱出方案，复制一份基础方案继续购买
                        plan = dp[i - 1][planIndex].createSnapshot();
                    }
                }
                // 无论主件附件都是需要加进方案判断的
                plan.addGoods(goods);
                // 看看新生成的计划有没有超过目前的钱
                if (plan.getTotalPrice() <= j * gcd) {
                    // 如果钱够，则比较上个商品使用这么多钱的方案，然后再判断哪个方案的满意度高，择优获取
                    dp[i][j] = ShoppingPlan.max(dp[i - 1][j], plan);
                    continue;
                }
                // 不够钱买新方案的，那就用上个商品在这个钱的方案
                dp[i][j] = dp[i - 1][j];
            }
        }
        // 将最终的方案返回
        return dp[n][m];
    }

    /**
     * 商品
     */
    public static class Goods {
        // 商品编号
        private int id;
        // 商品单价
        private int price;
        // 商品价值（满意度）
        private int value;
        // 商品类型（主件为0，附件大于0）
        private int type;

        public Goods(int id, int price, int value, int type) {
            this.id = id;
            this.price = price;
            this.value = value;
            this.type = type;
        }

        public int getId() {
            return this.id;
        }

        public int getPrice() {
            return this.price;
        }

        public int getValue() {
            return this.value;
        }

        public int getType() {
            return this.type;
        }

        /**
         * 商品是否附件
         * @return true/false
         */
        public boolean isAttachment() {
            return this.type > 0;
        }
    }

    /**
     * 购物方案
     */
    public static class ShoppingPlan {
        // 商品列表
        private List<Goods> goodsList;
        // 总金额
        private int totalPrice;
        // 总价值（总满意度）
        private int totalValue;

        /**
         * 构造函数，需要输入方案编号
         */
        public ShoppingPlan() {
            this.goodsList = new ArrayList<Goods>();
            this.totalPrice = 0;
            this.totalValue = 0;
        }

        private ShoppingPlan(List<Goods> goodsList, int totalPrice, int totalValue) {
            this.goodsList = goodsList;
            this.totalPrice = totalPrice;
            this.totalValue = totalValue;
        }

        /**
         * 添加商品，同时会累计总金额和总价值
         * @param goods 商品
         */
        public void addGoods(Goods goods) {
            this.goodsList.add(goods);
            this.totalPrice += goods.getPrice();
            this.totalValue += goods.getValue();
        }

        public int getTotalPrice() {
            return this.totalPrice;
        }

        public int getTotalValue() {
            return this.totalValue;
        }

        /**
         * 判断方案中是否存在当前附件的主件
         * @param attachment 附件商品
         * @return true/false
         */
        public boolean hasMainGoods(Goods attachment) {
            for (Goods mainGoods : this.goodsList) {
                if (mainGoods.getId() == attachment.getType()) {
                    return true;
                }
            }
            return false;
        }

        /**
         * 复制购物方案（不会影响到原购物方案信息）
         * @return 购物方案副本
         */
        public ShoppingPlan createSnapshot() {
            List<Goods> goodsList = new ArrayList<Goods>(this.goodsList.size());
            goodsList.addAll(this.goodsList);
            return new ShoppingPlan(goodsList, this.totalPrice, this.totalValue);
        }

        /**
         * 获取满意度高的方案
         * @param a 购物方案a
         * @param b 购物方案b
         * @return 满意度高的方案
         */
        public static ShoppingPlan max(ShoppingPlan a, ShoppingPlan b) {
            if (a.getTotalValue() >= b.getTotalValue()) {
                return a;
            }
            return b;
        }
    }

    /**
     * 用更相减损法计算公约数
     * @param a 数a
     * @param b 数b
     * @return 最大公约数
     */
    public static int gcd(int a, int b) {
        if (a < b) {
            int tmp = a;
            a = b;
            b = tmp;
        }
        return (a % b == 0) ? b : gcd(a - b, b);
    }

    /**
     * 计算数组里的所有数的最大公约数
     * @param goodsList 源数据数组
     * @return 数组里的所有数的最大公约数
     */
    public static int getArrayGcd(List<Goods> goodsList) {
        int gcd = goodsList.get(0).getPrice();
        for (int i = 1; i < goodsList.size(); i++) {
            gcd = gcd(gcd, goodsList.get(i).getPrice());
        }
        return gcd;
    }
}

这个题是背包问题的变种，基础解法是二维动态规划。不过，由于加了主件和附件的限制，需要判断的东西一下子多了很多。本人脑子不够用，就将有可能用到的西信息封装起来了，一共是两个类：ShoppingPlan（购物方案）和Goods（商品）

商品的基础属性是不会变的，通过调整购物方案里的商品列表做动态规划达到最优。

说一下动态规划二位数组的生成思路。

如果是一维的动态规划，我们可以知道它的思路是递推，也就是前面方案作为基础方案不断积累，数组的最后一个元素dp[n]就是最后的结果。一维的题，一般每一步都是一定会发生，且有规律的，只是发生的时间有交错。

沿着一维动态规划的思路拓展到二维，那就是经典的背包问题，按每件物品的选取累计，但是跟一维不同的是，物品可选可不选，这样就衍生出了分支，所以需要使用二维来记录分支。然后通过前两个物品选出来的方案作为基础，用上一个物品加入基础方案，和当前物品加入基础方案，这两个方案作比较，择优设置到当前的方案中。

背包数组的纵向是物品，横向记录了选取和不选取的值

回到商品选取，商品选取的话大致思路是按照背包问题构筑的，由于加入了主件附件联动，我们需要考虑以下问题：

1.当前的商品是否附件，如果是就需要跟主件一起计算金额

2.基础方案是否包含了主件，如果包含的话，就不能将主件再加到购物方案里面了，只能加附件

3.如果基础方案没有主件，那么我需要腾出钱去买主件，如果剩下的钱不够了，我还需要换一个基础方案，再加上主件附件，然后去比较

梳理之后，发现问题可以按以下思路解决：

1.判断商品是否附件，如果是主件，那么直接看钱够不够，然后跟上个商品在这个钱的旧方案比较就好

2.如果是附件，那么一直加钱，直到满足有一个基础方案+附件的新方案出来，如果没有，就用同价格上个商品的方案

3.判断基础方案中是否已存在主件，如果不存在主件的话，加上主件的价格，一直加钱，直到有一个基础方案+主件+附件的新方案出来，没有的话，用铜价格上个商品的方案

最后发现，同时满足钱够且满意度高才会替换方案，所以最后二维数组最后一个元素就是最优的购物方案。

由于按1块钱去构造数组和循环，会产生大量的同样的方案，且处理时间非常长，所以采用了求取商品数组的最大公约数简化数组的构成和缩短计算时间。

import java.util.Objects;
import java.util.Scanner;

public class Interview {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();
        String[] priceAndNum = input.split(" ");
        int price = Integer.parseInt(priceAndNum[0]);
        int num = Integer.parseInt(priceAndNum[1]);
        Goods[] goodsList = new Goods[num];
        for (int i = 0; i < num; i++) {
            String goodsInfo = scanner.nextLine();
            String[] goodsArray = goodsInfo.split(" ");
            Goods goods = new Goods();
            goods.setPrice(Integer.parseInt(goodsArray[0]));
            goods.setSatisfy(Integer.parseInt(goodsArray[1]));
            goods.setAttachId(Integer.parseInt(goodsArray[2]));
            goodsList[i] = goods;
        }
        for (int i = 0; i < num; i++) {
            Goods goods = goodsList[i];
            if (goods.attachId > 0) {
                Goods main = goodsList[goods.attachId - 1];
                if (Objects.isNull(main.getFirstAttach())) {
                    main.setFirstAttach(i);
                } else {
                    main.setSecondAttach(i);
                }
            }
        }
        int [][] dp = new int[num + 1][price + 1];
        //遍历所有商品
        for (int i = 1; i <= num; i++) {
            Goods goods = goodsList[i - 1];
            //4中情况 1：主件 2：主件+附件1 3：主件+附件2 4：主件+附件1+附件2
            int mainSatisfy = goods.price * goods.satisfy;
            boolean ifAttach1 = Objects.nonNull(goods.firstAttach);
            boolean ifAttach2 = Objects.nonNull(goods.secondAttach);
            int attach1Price = ifAttach1 ? goodsList[goods.firstAttach].price : 0;
            int attach2Price = ifAttach2 ? goodsList[goods.secondAttach].price : 0;
            int attach1Satisfy = ifAttach1 ? mainSatisfy + goodsList[goods.firstAttach].satisfy * goodsList[goods.firstAttach].price : 0;
            int attach2Satisfy = ifAttach2 ? mainSatisfy + goodsList[goods.secondAttach].satisfy * goodsList[goods.secondAttach].price : 0;
            int attach1And2 = ifAttach2 && ifAttach1 ? attach1Satisfy + attach2Satisfy - mainSatisfy : 0;
            //遍历预算，动态找出满足价格范围内的最大满意度
            for (int j = 1; j <= price; j++) {
                dp[i][j] = dp[i - 1][j];
                if (goods.attachId > 0) {
                    //如果是附件，那么不放dp，dp的值为放进一件、两件、三件...商品时的最大满意度
                    continue;
                }
                if (j - goods.price >= 0) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - goods.price] + mainSatisfy);
                }
                if (ifAttach1 && (j - (goods.price + attach1Price) >= 0)) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - goods.price - attach1Price] + attach1Satisfy);
                }
                if (ifAttach2 && (j - (goods.price + attach2Price) >= 0)) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - goods.price - attach2Price] + attach2Satisfy);
                }
                if (ifAttach1 && ifAttach2 && (j - (goods.price + attach1Price + attach2Price) >= 0)) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - goods.price - attach1Price - attach2Price] + attach1And2);
                }
            }
        }
        System.out.println(dp[num][price]);
    }


    static class Goods {
        private Integer price;
        private Integer satisfy;
        private Integer attachId;

        private Integer firstAttach;

        private Integer secondAttach;

        public Integer getPrice() {
            return price;
        }

        public void setPrice(Integer price) {
            this.price = price;
        }

        public Integer getSatisfy() {
            return satisfy;
        }

        public void setSatisfy(Integer satisfy) {
            this.satisfy = satisfy;
        }

        public Integer getAttachId() {
            return attachId;
        }

        public void setAttachId(Integer attachId) {
            this.attachId = attachId;
        }

        public Integer getFirstAttach() {
            return firstAttach;
        }

        public void setFirstAttach(Integer firstAttach) {
            this.firstAttach = firstAttach;
        }

        public Integer getSecondAttach() {
            return secondAttach;
        }

        public void setSecondAttach(Integer secondAttach) {
            this.secondAttach = secondAttach;
        }
    }
}

import java.util.*;

public class Main {

public static void main(String[] args) {

    Scanner in = new Scanner(System.in);

    int N = in.nextInt();

    int m = in.nextInt();

    int[] v = new int[m + 1]; //价格

    int[] p = new int[m + 1]; //重要度

    int[] q = new int[m + 1]; //所属主件编号

    for (int i = 1 ; i 1 ; i++) {

        v[i] = in.nextInt();

        p[i] = in.nextInt();

        q[i] = in.nextInt();

    }

    System.out.println(getMaxSat(v, p, q, N, m));

}

//获取最大满意值方法

public static int getMaxSat(int[] v, int[] p, int[] q, int N, int m) {

    Good[][] good = new Good[m + 1][3]; //g[i][j]表示i号物品的第j个附件（最多2个），i=0表示i号商品是主件，g[i][0]为空表示i号商品为附件

    int max = 0;

    int[] sat = new int [N + 1]; //sat[i]表示花费i元时的满意度

    //跟据条件初始化good对象数组

    for (int i = 1 ; i <= m ; i++) {

        Good gt = new Good(v[i], v[i] * p[i]);

        if (q[i] == 0) {

            good[i][0] = gt;

        } else { //是附件时判断是否存在另一个附件

            if (good[q[i]][1] == null)

                good[q[i]][1] = gt;

            else

                good[q[i]][2] = gt;

        }

    }

    for (int i = 1; i <= m; i++) {

        for (int j = N; j >= 0; j--) {

            Good gt0 = good[i][0];

            Good gt1 = good[i][1];

            Good gt2 = good[i][2];

            // i号商品不是主件时跳过循环

            if (gt0 == null)

                break;

            // 第i号物品为主件时列出四种情况：主，主+附1，主+附2，主+附1+附2，并记录四种情况下的最大的满意度

            else {

                //该主件没有附件

                if (gt1 == null && gt2 == null) {

                    if (gt0.v <= j) {

                        //和原来的sat[j]比较，取最大满意度并记录

                        sat[j] = Math.max(sat[j], gt0.vp + sat[j - gt0.v]);

                    }

                }

                //该主件有1个附件，若剩余金额允许购买主件和附件，比较主和主+附1的最大满意度

                if (gt1 != null) {

                    if (gt0.v <= j) {

                        sat[j] = Math.max(sat[j], gt0.vp + sat[j - gt0.v]);

                    }

                    if (gt0.v + gt1.v <= j) {

                        sat[j] = Math.max(sat[j], gt0.vp + gt1.vp + sat[j - gt0.v - gt1.v]);

                    }

                }

                //该主件有2个附件，若剩余金额允许购买主件和附件，比较主，主+附1，主+附2，主+附1+附2的最大满意度

                if (gt2 != null) {

                    if (gt0.v <= j) {

                        sat[j] = Math.max(sat[j], gt0.vp + sat[j - gt0.v]);

                    }

                    if (gt0.v + gt1.v <= j) {

                        sat[j] = Math.max(sat[j], gt0.vp + gt1.vp + sat[j - gt0.v - gt1.v]);

                    }

                    if (gt0.v + gt2.v <= j) {

                        sat[j] = Math.max(sat[j], gt0.vp + gt2.vp + sat[j - gt0.v - gt2.v]);

                    }

                    if (gt0.v + gt1.v + gt2.v <= j) {

                        sat[j] = Math.max(sat[j], gt0.vp + gt1.vp + gt2.vp + sat[j - gt0.v - gt1.v - gt2.v]);

                    }

                }

            }

        }

    }

    return sat[N];

}

}

//定义商品类

class Good {

int v;//价格

int vp;//满意度

public Good(int v, int vp) {

    this.v = v;

    this.vp = vp;

}

}

import java.util.ArrayList;
import java.util.List;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.concurrent.ConcurrentHashMap;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer line = new StringTokenizer(br.readLine());
        int money = Integer.parseInt(line.nextToken());
        int num = Integer.parseInt(line.nextToken());

        Good[] goods = new Good[num];
        int i = 0;
        while (i < num) {
            line = new StringTokenizer(br.readLine());
            int v = Integer.valueOf(line.nextToken());
            int p = Integer.valueOf(line.nextToken());
            int q = Integer.valueOf(line.nextToken());
            if (goods[i] == null) {
                goods[i] = new Good(v, p, q);
            } else {
                goods[i].v = v;
                goods[i].p = p;
                goods[i].q = q;
            }
            if (q > 0) { // 附件
                if (goods[q - 1] == null) { // 主件还未创建
                    goods[q - 1] = new Good(0, 0, 0);
                }
                if (goods[q - 1].g1 < 0) {
                    goods[q - 1].g1 = i;
                } else {
                    goods[q - 1].g2 = i;
                }
            }
            i++;
        }

        System.out.println(shopping(goods, money));
    }



    public static int shopping(Good[] goods, int money) {
        int dp[] = new int[money + 1];
        for (int i = 0; i < goods.length; i++) {
            Good g = goods[i];
            for (int j = money; j >= g.v && g.q == 0; j--) {
                // 只买主件
                dp[j] = Math.max(dp[j - g.v] + g.p * g.v, dp[j]);
                // 主 + 附1
                if (g.g1 >= 0 && j >= (g.v + goods[g.g1].v)) {
                    Good g1 = goods[g.g1];
                    dp[j] = Math.max(dp[j - g.v - g1.v] + g.p * g.v + g1.v * g1.p, dp[j]);
                }

                // 主 + 附2
                if (g.g2 >= 0 && j >= (g.v + goods[g.g2].v)) {
                    Good g2 = goods[g.g2];
                    dp[j] = Math.max(dp[j - g.v - g2.v] + g.p * g.v + g2.v * g2.p, dp[j]);
                }
                // 主 + 附1 + 附2
                if (g.g1 >= 0 && g.g2 >= 0 && j >= (g.v + goods[g.g1].v + goods[g.g2].v)) {
                    Good g1 = goods[g.g1];
                    Good g2 = goods[g.g2];
                    dp[j] = Math.max(dp[j - g.v - g1.v - g2.v] + g.p * g.v + g1.v * g1.p + g2.v *
                                     g2.p, dp[j]);
                }
            }
        }
        return dp[money];
    }


    public static class Good {
        private int v; // 价格
        private int p; // 重要性
        private int q; // 主件id
        private int g1 = -1; // 附件1
        private int g2 = -1; // 附件2

        public Good(int v, int p, int q) {
            this.v = v;
            this.p = p;
            this.q = q;
        }
    }
}