题解 | #购物单#

使用两个数组：price[][],plusImportant[][]分别存储，主件、附件价格以及对应的重要度乘积 price第1列代表着主件的价格，例如price[1][1]代表第一个主件的价格 第2列代表附件1的价格，例如price[2][1]代表第一个主件的第一个附件的价格。。。依次类推 plusImportant数组也是同理类推

输入处理，如果输入的q == 0；则说明是主件，写入price[i][0]的位置，否则，写入prive[q][1]/price[q][2]的位置

动态求解，dp的动态转移方程:dp[money] = max(dp[j],dp[j - 选入的价格] + 重要度); 一共分四种情况:

1. 直接购买主件
2. 购买主件 + 附件1
3. 购买主件 + 附件2
4. 购买主件 + 附件1 + 附件2 最后求得的dp[money]就是结果.

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextInt()){
            int money = sc.nextInt() / 10;// 输入目标金额
            int nums = sc.nextInt();// 输入循环次数,有多少件物品
            int[][] price = new int[nums + 1][3];// 用来存储主件 附件1 附件2 的价格
            int[][] plusImportan = new int[nums + 1][3];// 用来存储主件 附件1 附件2 的重要度（价格*重要度p）
            // 处理输入
            for(int i = 1;i <= nums;i++){
                int v = sc.nextInt() / 10;// 这个是主件价格
                int p = sc.nextInt();// 这个是输入的重要度
                int q = sc.nextInt();// 这个用来判断是主件还是附件，0是主件
                if(q == 0){
                    // 如果q为0，就是主件
                    price[i][0] = v;// 数组price的第1列为主键价格
                    plusImportan[i][0] = v * p;// plusImportant的第一列为价格 * 重要度
                }else if(price[q][1] == 0){
                    // 如果不是主件，并且第二列为空，那就写入第二列,写入第q个位置，而不是第i个位置了
                    price[q][1] = v;
                    plusImportan[q][1] = v * p;
                }else{
                    // 写入附件2的位置
                    price[q][2] = v;
                    plusImportan[q][2] = v * p;
                }
            }

            // 处理完输入数据，就完成动态规划
            int[] dp = new int[money + 1];// 转移方程: Max(dp[当前金额],dp[当前金额 - 待加入的金额] + 重要度])
            for(int i = 1;i <= nums; i++){
                if(price[i][0] == 0)// 当前主件为空
                    continue;// 继续循环
                for(int j = money; j >= price[i][0];j--){
                    // 从最大开始往前推，求出dp[money]的最优解
                    // 先将数据从数组中取出来
                    int a = price[i][0];
                    int a1 = plusImportan[i][0];
                    int b = price[i][1];
                    int b1 = plusImportan[i][1];
                    int c = price[i][2];
                    int c1 = plusImportan[i][2];
                    if (j >= a) {
                        // 如果能够买的下当前物品
                        dp[j] = Math.max(dp[j],dp[j - a] + a1);// 求解重要度
                    }
                    if(j >= a + b){
                        dp[j] = Math.max(dp[j],dp[j - a - b] + a1 + b1);// 求解重要度
                    }
                    if(j >= a + c){
                        dp[j] = Math.max(dp[j],dp[j - a  - c] + a1 + c1);// 求解重要度
                    }
                    if(j >= a + b + c){
                        dp[j] = Math.max(dp[j],dp[j - a - b - c] + a1 + b1 + c1);// 求解重要度
                    }
                }
            }
            System.out.println(dp[money] * 10);
    }
    }
}