题解 | #购物单#

动态规划

import java.util.Scanner;
import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static int result = 0;
    public static List<int[]> list = new ArrayList<>();
    public static int sum = 0;
    public static int station = 0;
    public static int totalMoney;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            totalMoney = in.nextInt() / 10;
            int totalCount = in.nextInt();
            good[] goods = new good[totalCount];
            for (int i = 0; i < totalCount; i++) {
                int value = in.nextInt() / 10;
                int imp = in.nextInt();
                int att = in.nextInt();
                goods[i] = new good(value, imp, att);
            }
            for (int i = 0; i < totalCount; i++) {
                if(goods[i].a > 0) {
                    int zhujian = goods[i].a - 1;
                    if (goods[zhujian].a1 == -1) {
                        goods[zhujian].a1 = i;
                    } else {
                       goods[zhujian].a2 = i;
                    }
                }
            }
            findStation(goods, totalMoney);
        }

    }
    /**
       dp[i][j] 表示 前 i个 商品 最大花费j 元 所获得的最大满意度
       状态转移矩阵 dp[i][j] = max(dp[i - 1][j], dp[i -1][j - v] + sta);
    */
    public static void findStation (good[] goods, int totalMoney) {
       int[][] dp = new int[goods.length + 1][totalMoney + 1];
        dp[0][0] = 0;
        for (int i = 1; i < goods.length + 1; i++) {
            for (int j = 1; j < totalMoney + 1; j++) {
                good tempGood = goods[i - 1];
                if (tempGood.a != 0) { // 如果是附件 dp[i][j] = dp[i -1][j];
                    dp[i][j] = dp[i - 1][j];
                    continue;
                } else {
                    dp[i][j] = dp[i - 1][j];
                    int v1 = tempGood.v;
                    if (j >= v1) { // 只买主件
                        int sta1 = tempGood.v * tempGood.i;
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v1] + sta1);
                    }
                    if (tempGood.a1 != -1) { //买主件和附件1
                        good goodA1 = goods[tempGood.a1];
                        int v2 = tempGood.v + goodA1.v;
                        if (j >= v2) {
                            int sta2  = tempGood.v * tempGood.i + goodA1.v * goodA1.i;
                            dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v2] + sta2);
                        }
                    }
                    if (tempGood.a2 != -1) { //买主件和附件2
                        good goodA2 = goods[tempGood.a2];
                        int v3 = tempGood.v + goodA2.v;
                        if (j >= v3) {
                            int sta3 = tempGood.v * tempGood.i + goodA2.v * goodA2.i;
                            dp[i][j] = Math.max(dp[i][j], dp[i - 1][j -v3] + sta3);
                        }
                    }
                    if (tempGood.a1 != -1 && tempGood.a2 != -1) { // 买主件和附件1附件2
                        good goodA1 = goods[tempGood.a1];
                        good goodA2 = goods[tempGood.a2];
                        int v4 = tempGood.v + goodA1.v + goodA2.v;
                        if (j >= v4) {
                            int sta4 = tempGood.v * tempGood.i + goodA1.v * goodA1.i + goodA2.v * goodA2.i;
                            dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v4] + sta4);
                        }
                    }
                }
            }
        }
       System.out.println(dp[goods.length][totalMoney] * 10);
    }
    
    public static class good {
        int v;
        int i;
        int a;
        int a1 = -1;
        int a2 = -1;
        public good(int v, int i, int a) {
            this.v = v;
            this.i = i;
            this.a = a;
        }
    }
}