import java.util.*;

public class Main {
    static int N = 70, M = 32010;
    static int[][] f = new int[N][M];
    static int n, m;
    static int[][] master = new int[N][2]; // 主件
    static List<int[]>[] servant = new ArrayList[N];//附件

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();
        //初始化
        for (int i = 1; i <= n; i++) {
            master[i] = new int[]{0, 0};
            servant[i] = new ArrayList<>();
        }
        for (int i = 1; i <= n; i++) {
            int v = sc.nextInt();
            int w = sc.nextInt();
            int p = sc.nextInt();
            if (p == 0) master[i] = new int[]{v, v * w};//表示主件，所以创建存价格跟价值
            else servant[p].add(new int[]{v, v * w});//将价格跟价值 放到对应主件p的链表下
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                //一个背包表示的就是主件+附件的数量
                //比如00 01 10 11  各组含义就是一个没选，选了第一个，选了第二个，两个都选

                f[i][j] = f[i - 1][j]; //这是不选第i组背包

                //二进制，主件对应的附件的二进制枚举
                for (int k = 0; k < 1 << servant[i].size(); k++) {
                    // 这是枚举00 01 10 11但是这是最大情况 ，
                    //如果他的附件只有1个，那么就只需要枚举0 1，这两种情况就行

                    //主件的价格 跟 价值
                    int v = master[i][0];
                    int w = master[i][1];
                    for (int u = 0; u < servant[i].size(); u++) {
                        if ((k >> u & 1) == 1) {    //二进制上面是0就不选，1就表示选
                            v += servant[i].get(u)[0];
                            w += servant[i].get(u)[1];

                        }
                    }
                    if (j >= v) f[i][j] = Math.max(f[i][j], f[i - 1][j - v] + w);
                }
            }
        }
        System.out.println(f[n][m]);
    }
}

创建对象写法，速度差不多

import java.util.*;

public class Main {
    static class PII {
        int v, w;

        public PII(int v, int w) {
            this.v = v;
            this.w = w;
        }
    }

    static int N = 70, M = 32010;
    static int[][] f = new int[N][M];
    static int n, m;
    static PII[] master = new PII[N];
    static List<PII>[] servant = new ArrayList[N];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] str = sc.nextLine().split(" ");
        m = Integer.parseInt(str[0]);
        n = Integer.parseInt(str[1]);
        for (int i = 1; i <= n; i++) {
            master[i] = new PII(0, 0);
            servant[i] = new ArrayList<>();
        }
        for (int i = 1; i <= n; i++) {
            str = sc.nextLine().split(" ");
            int v = Integer.parseInt(str[0]);
            int w = Integer.parseInt(str[1]);
            int p = Integer.parseInt(str[2]);
            if (p == 0) master[i] = new PII(v, v * w);
            else servant[p].add(new PII(v, v * w));
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                f[i][j] = f[i - 1][j];

                for (int k = 0; k < 1 << servant[i].size(); k++) {
                    int v = master[i].v;
                    int w = master[i].w;
                    for (int u = 0; u < servant[i].size(); u++) {
                        if ((k >> u & 1) == 1) {
                            v += servant[i].get(u).v;
                            w += servant[i].get(u).w;

                        }
                    }
                    if (j >= v) f[i][j] = Math.max(f[i][j], f[i - 1][j - v] + w);
                }

            }
        }
        System.out.println(f[n][m]);
    }
}