题解 | #购物单#

这样的题只配中等难度吗？那困难级别的得多变态呀。。。

在搞懂了0/1背包问题，完全背包问题，多重背包问题之后，在明知道这道题就是背包问题的扩展，应该使用动态规划解决的背景下，耗时40多分钟，仍然无法想到一个应用简单类型就能解决此题的方案。最终只好新建一个类来解决，再耗时1小时才解决此问题。

此题最大的难点在于：如何在加入附件的时候确定主件已经加入了，如何在处理附件2的时候确定附件1或者主件是否加入了，如何确定主件，主件+附件1，主件+附件2和主件+所有附件哪个才是最优解。

我的方案是使用一个自定义的类来记录主附件之间的关系，数组中只会记录主件，附件随同主件一起处理。

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

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] values = scanner.nextLine().split(" ");
        int money = Integer.parseInt(values[0]) / 10;
        int count = Integer.parseInt(values[1]);
        Good[] goods = new Good[count + 1];
        for (int i = 1; i <= count; i++) {
            values = scanner.nextLine().split(" ");
            int price = Integer.parseInt(values[0]) / 10;
            int weight = Integer.parseInt(values[1]);
            int index = Integer.parseInt(values[2]);
            if (index == 0) { // master 才放
                Good good = goods[i];
                if (good == null) {
                    goods[i] = new Good(price, weight);
                } else {
                    good.price = price;
                    good.weight = weight;
                }
            } else {
                Good master = goods[index];
                if (master == null) {
                    master = new Good();
                    goods[index] = master;
                }
                master.slaves.add(new Good(price, weight));
            }
        }
        System.out.println(plan1(money, goods));
    }

    private static int plan1(int money, Good[] goods) {
        int[] dp = new int[money + 1];
        for (int i = 1; i < goods.length; i++) {
            Good master = goods[i];
            if (master == null) {
                continue;
            }
            for (int j = money; j >= master.price; j--) {
                // 单独主
                int masterValue = master.price * master.weight;
                int masterOnly = dp[j - master.price] + masterValue;
                dp[j] = Math.max(dp[j], masterOnly);
                if (master.slaves.size() == 0) {
                    continue;
                }
                // 主+1
                Good slave0 = master.slaves.get(0);
                int price0 = master.price + slave0.price;
                if (j >= price0) {
                    int masterAndOne = dp[j - price0] + masterValue + slave0.price * slave0.weight;
                    dp[j] = Math.max(dp[j], masterAndOne);
                }
                if (master.slaves.size() == 1) {
                    continue;
                }
                // 主+2
                Good slave1 = master.slaves.get(1);
                int price1 = master.price + slave1.price;
                if (j >= price1) {
                    int masterAndTwo = dp[j - price1] + masterValue + slave1.price * slave1.weight;
                    dp[j] = Math.max(dp[j], masterAndTwo);
                }

                // 主+1+2
                int priceAll = master.price + slave0.price + slave1.price;
                if (j >= priceAll) {
                    int all = dp[j - priceAll] + masterValue + slave0.price * slave0.weight + slave1.price * slave1.weight;
                    dp[j] = Math.max(dp[j], all);
                }
            }
        }
        return dp[money] * 10;
    }

    private static class Good {
        int price;
        int weight;
        List<Good> slaves = new ArrayList<>(2);

        Good() {
        }

        Good(int price, int weight) {
            this.price = price;
            this.weight = weight;
        }
    }

}