题解 | #购物单#

import java.util.Scanner;

public class Test1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int sumMoney = sc.nextInt();
            sumMoney = sumMoney / 10;//价格都是10的倍数，缩小状态空间
            int numGoods = sc.nextInt();
            int[][] price = new int[numGoods + 1][3];
            int[][] importance = new int[numGoods + 1][3];
            for(int i = 1;i <= numGoods;i++){
                int a = sc.nextInt(),b = sc.nextInt(),c = sc.nextInt();
                a = a / 10;
                if(c == 0){//主件
                    price[i][0] = a;//主键价格
                    importance[i][0] = a * b;
                }else{
                    if(price[c][1] == 0){//附件1不存在
                        price[c][1] = a;
                        importance[c][1] = a * b;
                    }else{//附件1已存在，那么为附件2
                        price[c][2] = a;
                        importance[c][2] = a * b;
                    }
                }
            }
            int[] dp = new int[sumMoney + 1];
            //输入处理完毕，分组背包解决问题
            for(int i = 1;i <= numGoods;i++){//每个商品只能用一次所以先遍历商品
                if(price[i][0] == 0) continue;//是附件直接跳过
                for(int j = sumMoney;j >= price[i][0];j--){//保存上一阶段的状态，所以倒叙
                    int a = price[i][0],b = importance[i][0];
                    int c = price[i][1],d = importance[i][1];
                    int e = price[i][2],f = importance[i][2];
                    dp[j] = Math.max(dp[j],dp[j - a] + b);//情况1:只计算主件
                    dp[j] = j >= (a + c) ? Math.max(dp[j],dp[j - a - c] + b + d) : dp[j];//情况2：计算主件和附件1
                    dp[j] = j >= (a + e) ? Math.max(dp[j],dp[j - a - e] + b + f) : dp[j];//情况3：计算主件和附件2
                    dp[j] = j >= (a + c + e) ? Math.max(dp[j],dp[j - a - e - c] + b + f + d) : dp[j];//情况4：计算主件和附件1和附件2
                }
            }
            System.out.println(dp[sumMoney] * 10);
        }

    }
}