题解 | #购物单#

import java.util.Scanner;

/**
 * 【购物单】
 *
 *  描述：王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的
 *      必须先买该附件所属的主件，且每件物品只能购买一次
 *      每件物品规定了一个重要度，用整数 1 ~ 5 表示
 *
 *  要求：希望在花费不超过 N 元的前提下，使自己的满意度达到最大
 *  
 *  【解题思路】：主要是理解动态规划算法。  ps:太难了，理解加调试花了好几天!
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 输入
        int totalMoney = sc.nextInt();
        int goodNumber = sc.nextInt();

        // 录入物品信息
        Good[] goodArray = new Good[goodNumber + 1];
        int masterCount = 0;
        for (int i = 1; i <= goodNumber; i++) {
            Good good = new Good();
            good.setPrice(sc.nextInt());
            good.setWeight(sc.nextInt());
            good.setNo(sc.nextInt());
            goodArray[i] = good;
          	// 统计主件的个数，为后面创建主件数组做准备
            if (good.getNo() == 0) {
                masterCount++;
            }
        }
      
        // 创建仅包含主件的数组，并设置主件、附件从属关系
        Good[] masterArray = new Good[masterCount + 1];
        for (int i = 1, j = 1; i < goodArray.length; i++) {
            int no = goodArray[i].getNo();
            if (no > 0) {
                if (goodArray[no].getSlaveOne() == null) {
                    goodArray[no].setSlaveOne(goodArray[i]);
                } else {
                    goodArray[no].setSlaveTwo(goodArray[i]);
                }
            } else {
                masterArray[j] = goodArray[i];
                j++;
            }
        }
      
        // 动态规划数组
        int[][] dp = new int[masterCount + 1][totalMoney + 10];
        for (int i = 1; i < masterCount + 1; i++) {
            // 价格都是10的倍数，步进取10可以减少遍历次数
            for (int money = 10; money < totalMoney + 10; money = money + 10) {
                // 分别记录4种情况的花费和满意度，每个存储单元记录1种，不存在则为0
                int[] costMoney = new int[4];
                int[] satisfiedLevel = new int[4];

                // 情况1：仅主件的价格与满意度
                satisfiedLevel[0] = masterArray[i].getPrice() * masterArray[i].getWeight();
                costMoney[0] = masterArray[i].getPrice();
              
                // 情况2：主件+附件1的价格与满意度
                if (masterArray[i].getSlaveOne() != null) {
                    satisfiedLevel[1] = satisfiedLevel[0] + masterArray[i].getSlaveOne().getPrice() * masterArray[i].getSlaveOne().getWeight();
                    costMoney[1] =  costMoney[0] + masterArray[i].getSlaveOne().getPrice();
                }
              
                // 情况3：主件+附件2的价格与满意度
                if (masterArray[i].getSlaveTwo() != null) {
                    satisfiedLevel[2] = satisfiedLevel[0] + masterArray[i].getSlaveTwo().getPrice() * masterArray[i].getSlaveTwo().getWeight();
                    costMoney[2] =  costMoney[0] + masterArray[i].getSlaveTwo().getPrice();
                }
              
                // 情况4：主件+附件1+附件2的价格与满意度
                if (masterArray[i].getSlaveOne() != null && masterArray[i].getSlaveTwo() != null) {
                    Good slaveOne = masterArray[i].getSlaveOne();
                    Good slaveTwo = masterArray[i].getSlaveTwo();
                    satisfiedLevel[3] = satisfiedLevel[0] + slaveOne.getPrice() * slaveOne.getWeight() + slaveTwo.getPrice() * slaveTwo.getWeight();
                    costMoney[3] = costMoney[0] + slaveOne.getPrice() + slaveTwo.getPrice();
                }

                int temp = 0;  // 临时保存4种情况下的最优解
                for (int j = 0; j < costMoney.length; j++) {
                    // 不涉及的情况跳过
                    if (costMoney[j] == 0) {
                        continue;
                    }
                  	// 关键来了
                    if (costMoney[j] > money) {
                        dp[i][money] =  dp[i - 1][money];
                    } else {
                        temp = Math.max(dp[i - 1][money], dp[i - 1][money - costMoney[j]] + satisfiedLevel[j]);
                    }
                    dp[i][money] = Math.max(temp, dp[i][money]);
                }
            }
        }
        System.out.println(dp[masterCount][totalMoney]);
    }
}




class Good {
    // 价格
    private int price;
    // 重要度
    private int weight;
    // 编号, 0表示主件，非0表示所属主件的编号
    private int no;
    // 附件1
    private Good slaveOne;
    // 附件2
    private Good slaveTwo;

    public int getPrice() {
        return price;
    }

    public void setPrice(int price) {
        this.price = price;
    }

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }

    public Good getSlaveOne() {
        return slaveOne;
    }

    public void setSlaveOne(Good slaveOne) {
        this.slaveOne = slaveOne;
    }

    public Good getSlaveTwo() {
        return slaveTwo;
    }

    public void setSlaveTwo(Good slaveTwo) {
        this.slaveTwo = slaveTwo;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }
}