题解 | #购物单#

动态规划

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);
        }

    }
    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++) {
               if (goods[i - 1].a != 0) {
                   dp[i][j] = dp[i -1][j];
               } else {
                   dp[i][j] = dp[i -1][j];
                   int vZhu = goods[i - 1].v; // 只填加主件
                   int totalImpZhu = vZhu * goods[i - 1].i;
                   if (j >= vZhu) dp[i][j] = Math.max(dp[i][j], dp[i -1][j - vZhu] + totalImpZhu);
                   // 添加主件 和附件1
                   if (goods[i - 1].a1 != -1 ) {
                       int VZhuAddA1 = vZhu + goods[goods[i - 1].a1].v;
                       if (j >= VZhuAddA1) {
                           int totalImportZhuAddA1 = totalImpZhu + goods[goods[i - 1].a1].v * goods[goods[i - 1].a1].i;
                           dp[i][j] = Math.max(dp[i][j], dp[i - 1][j- VZhuAddA1] + totalImportZhuAddA1);                       
                       }
                   } // 只添加附件1
                   if (goods[i - 1].a2 != -1 ) {
                       int vzhuAddA2 = goods[i - 1].v + goods[goods[i - 1].a2].v;
                       if (j >= vzhuAddA2) {
                           int totalimportZhuAddA2 = totalImpZhu + goods[goods[i - 1].a2].v * goods[goods[i - 1].a2].i;
                           dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - vzhuAddA2] + totalimportZhuAddA2); 
                       }
                   } // 只添加附件2
                   // 添加两个附件
                   if (goods[i - 1].a1 != -1 && goods[i - 1].a2 != -1) {
                       int vzhuAddA1AddA2 = vZhu + goods[goods[i - 1].a1].v + goods[goods[i - 1].a2].v;
                       if (j >= vzhuAddA1AddA2) {
                           int totalImportZhuAddA1AddA2 = totalImpZhu + goods[goods[i - 1].a1].v * goods[goods[i - 1].a1].i + goods[goods[i - 1].a2].v * goods[goods[i - 1].a2].i;
                           dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - vzhuAddA1AddA2] + totalImportZhuAddA1AddA2);  
                       }
                   } // 添加所有附件
               }
            }
        }
       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;
        }
    }
}