题解 | #购物单#一维数组逆序遍历

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        String a;
        String[] lineInfo;
        int m = 0, n = 0, i = 0, j = 0, k = 0, cnt = 0, mon = 0, impt = 0, inx = 0;
        int[] dp;
        int[] price = new int[4];
        int[] satfy = new int[4];
        int[][] cap, sub;
        try {
            a = r.readLine();
            lineInfo =
                a.split("\\s");//空格的转义字符是\s，split后面是跟正则表达式，\s在正则表达式中表示所有空位字符，用双斜杠区分；
            m = Integer.parseInt(lineInfo[0]);//总钱数
            n = Integer.parseInt(lineInfo[1]);//商品数量
            cap = new int[n][2];//主件数组
            sub = new int[n][4];//附件数组
            dp = new int[m + 1];//状态转移矩阵
            while (i < n) {
                a = r.readLine();
                lineInfo = a.split("\\s");
                mon = Integer.parseInt(lineInfo[0]);
                impt = Integer.parseInt(lineInfo[1]);
                inx = Integer.parseInt(lineInfo[2]);
                if (inx == 0) {//表示该商品为主件，放入cap
                    cap[i][0] = mon;
                    cap[i][1] = mon * impt;
                } else {//表示该商品为附件，放入sub
                    if (sub[inx - 1][0] == 0) {//表示该附件为主件的第一个附件
                        sub[inx - 1][0] = mon;
                        sub[inx - 1][1] = mon * impt;
                    } else {//表示该附件为主件的第二个附件，因为数组的前两个数据不为0，已经赋过值
                        sub[inx - 1][2] = mon;
                        sub[inx - 1][3] = mon * impt;
                    }
                }
                i++;
            }
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
        i = 0;//重置为0
        while (i < n) {
            if (cap[i][0] == 0) {
                i++;
                continue;//该索引位置处为附件，数据放入sub，因此跳过循环
            }
            price[0] = cap[i][0];
            satfy[0] = cap[i][1];
            cnt = 1; //表示该主件的遍历次数为1
            if (sub[i][0] != 0 && sub[i][2] == 0) {//有一个附件
                price[1] = cap[i][0] + sub[i][0];//主件和附件的组合，价格相加
                satfy[1] = cap[i][1] + sub[i][1];//主件和附件的组合，满意度相加
                cnt = 2;
            }
            if (sub[i][0] != 0 && sub[i][2] != 0) {//有两个附件
                price[1] = cap[i][0] + sub[i][0];//主件和一个附件的组合，价格相加
                satfy[1] = cap[i][1] +
                           sub[i][1];//主件和一个附件的组合，满意度相加
                price[2] = cap[i][0] + sub[i][2];//主件和一个附件的组合，价格相加
                satfy[2] = cap[i][1] +
                           sub[i][3];//主件和一个附件的组合，满意度相加
                price[3] = cap[i][0] + sub[i][0] +
                           sub[i][2];//主件和两个附件的组合，价格相加
                satfy[3] = cap[i][1] + sub[i][1] +
                           sub[i][3];//主件和两个附件的组合，满意度相加
                cnt = 4;
            }
            j = m;
            while (j >= 0) {
                k = 0;//重置
                while (k < cnt) {
                    if (j - price[k] >= 0) {
                        dp[j] = Math.max(dp[j], (dp[j - price[k]] + satfy[k]));
                    }
                    k++;
                }
                j -= 10;
            }
            i++;
        }
        System.out.print(dp[m]);
    }
}