题解 | #购物单#

```import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();       //预算金额
        N/=10;
        int m = sc.nextInt();       //商品件数
        int[][] price = new int[m+1][3];        //单件（含附件）价格统计
        int[][] weight = new int[m+1][3];       //单件（含附件）价格*重要程度 统计
        for (int i = 1; i <= m;i++){
            int v = sc.nextInt();               //价格
            int p = sc.nextInt();               //重要度
            int q = sc.nextInt();               //主附件
            //判断是否为主件
            v/=10;
            p*=v;
            if (q == 0){
                price[i][0] = v;
                weight[i][0] = p;
            }else if(price[q][1] == 0){                           //判断是第几件附件
                price[q][1] = v;
                weight[q][1] = p;
            }else {
                price[q][2] = v;
                weight[q][2] = p;
            }
        }
        
        int[][] ans = new int[m+1][N+1];
        for (int i = 1; i <= m;i++){
            for (int j = 1; j <= N;j++){
                int a = price[i][0];            //单主件
                int b = price[i][1];            //附件1
                int c = price[i][2];            //附件2
                int wa = weight[i][0];
                int wb = weight[i][1];
                int wc = weight[i][2];
                
                ans[i][j] = j - a >= 0?Math.max(ans[i-1][j],ans[i-1][j-a]+wa):ans[i-1][j];
                ans[i][j] = j - a - b >= 0?Math.max(ans[i][j],ans[i-1][j-a-b]+wa+wb):ans[i][j];
                ans[i][j] = j - a - c>= 0?Math.max(ans[i][j],ans[i-1][j-a-c]+wa+wc):ans[i][j];
                ans[i][j] = j - a - b -c>= 0?Math.max(ans[i][j],ans[i-1][j-a-b-c]+wa+wb+wc):ans[i][j];
            }
        }
        System.out.println(ans[m][N]*10);
    }
}