题解 | #购物单#

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int sumMoney = in.nextInt();
        int count = in.nextInt();

        Goods[] goods = new Goods[count + 1];
        int[][] arr = new int[count + 1][sumMoney + 1];

        for (int i = 1; i <= count; i++) {
            goods[i] = new Goods(0, 0, 0);

            goods[i].goodsSet(in.nextInt(), in.nextInt(), in.nextInt());
            goods[i].sumWeigh = goods[i].value * goods[i].weigh;

        }
        for (int i = 1; i <= count; i++) {
            if (goods[i].index != 0) {
                if (goods[goods[i].index].left == 0) {
                    goods[goods[i].index].left = i;
                } else if (goods[goods[i].index].right == 0) {
                    goods[goods[i].index].right = i;
                }
            }
        }

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


            for (int j = 1; j <= sumMoney; j++) {
                if (goods[i].index != 0) {
                    arr[i][j] = arr[i - 1][j];
                } else {
                    //三种情况
                    //第一种选择一个

                    arr[i][j] = arr[i - 1][j];
                    if (j >= goods[i].value)
                        arr[i][j] = Math.max(arr[i][j],arr[i - 1][j - goods[i].value] + goods[i].sumWeigh);
                    if (goods[i].left != 0 && j >= goods[i].value + goods[goods[i].left].value)
                        arr[i][j] = Math.max(arr[i][j], Math.max(arr[i - 1][j],arr[i - 1][j - goods[i].value - goods[goods[i].left].value] + goods[i].sumWeigh + goods[goods[i].left].sumWeigh));//选择left的

                    if (goods[i].right != 0 && j >= goods[i].value + goods[goods[i].right].value)
                        arr[i][j] = Math.max(arr[i][j], Math.max(arr[i - 1][j], arr[i - 1][j - goods[i].value - goods[goods[i].right].value] + goods[i].sumWeigh + goods[goods[i].right].sumWeigh));//选择right的
                    if (goods[i].left != 0 && goods[i].right != 0 &&
                            j >= goods[i].value + goods[goods[i].right].value + goods[goods[i].left].value)
                        arr[i][j] = Math.max(arr[i][j], Math.max(arr[i - 1][j], arr[i - 1][j - goods[i].value - goods[goods[i].right].value - goods[goods[i].left].value] + goods[i].sumWeigh + goods[goods[i].right].sumWeigh
 + goods[goods[i].left].sumWeigh));//选择all的
                }
            }
            /*
            100 2
            10 1
            20 0
            */
        }
        System.out.print(arr[count][sumMoney]);
    }
}
class Goods {
    int value;
    int weigh;
    int index;
    int sumWeigh;
    int sumValue;
    int left;
    int right;
    Goods(int v, int w, int i) {
        value = v;
        weigh = w;
        index = i;
    }
    void goodsSet(int v, int w, int i) {
        value = v;
        weigh = w;
        index = i;
    }
    public int setSumWeigh(int s) {
        sumWeigh = s;
        return s;
    }
    public int setSumValue(int s) {
        sumValue = s;
        return s;
    }
}