Java 题解 | #购物单#

先参考了一下评论区的思想，就是分成了不选择附件、选择一个附件（附件1或附件2）、选择两个附件三种情况，然后就是0-1背包问题了。

import java.util.*;

public class Main {


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        List<LinkedList<int[]>> goods = new ArrayList<>(m);
        for (int i = 0; i < m; i++) {
            goods.add(new LinkedList<>());
        }
        for (int i = 0; i < m; i++) {
            int num1 = scanner.nextInt();
            int num2 = scanner.nextInt();
            int num3 = scanner.nextInt();
            if (num3 == 0) {
                goods.get(i).addFirst(new int[]{num1, num2});
            } else {
                //附件添加到末尾
                goods.get(num3-1).addLast(new int[]{num1, num2});
            }
        }
        //移出空的good
        goods.removeIf(AbstractCollection::isEmpty);
        int[] dp = new int[n + 1];
        for (int i = 0; i < goods.size(); i++) {
            LinkedList<int[]> good = goods.get(i);
            for (int j = n; j >= good.get(0)[0]; j--) {
                //不管有没有附件,这步都要执行
                dp[j] = Math.max(dp[j], dp[j - good.get(0)[0]] + good.get(0)[1] * good.get(0)[0]);
                if (good.size() > 1) {
                    //选择一个附件，附件数大于1，选择一个附件这步都要执行
                    //选择一个附件有两种可能，选择附件1或者附件2，由于大于1 这里情况为选择附件1
                    if (j >= (good.get(0)[0] + good.get(1)[0])) {
                        dp[j] = Math.max(dp[j], dp[j - good.get(0)[0] - good.get(1)[0]] + good.get(0)[1] * good.get(0)[0] + good.get(1)[1] * good.get(1)[0]);
                    }

                }
                if (good.size() > 2) {
                    //同上选择一个附件有两种可能，选择附件1或者附件2，由于大于2 这里情况为选择附件2
                    if (j >= (good.get(0)[0] + good.get(2)[0])) {
                        dp[j] = Math.max(dp[j], dp[j - good.get(0)[0] - good.get(2)[0]] + good.get(0)[1] * good.get(0)[0] + good.get(2)[1] * good.get(2)[0]);
                    }
                    //选择两个附件 附件数大于2，选择两个附件这步都要执行
                    if (j >= (good.get(0)[0] + good.get(1)[0]+good.get(2)[0])) {
                        dp[j] = Math.max(dp[j], dp[j - good.get(0)[0] - good.get(1)[0] - good.get(2)[0]] + good.get(0)[1] * good.get(0)[0] + good.get(1)[1] * good.get(1)[0]+good.get(2)[1] * good.get(2)[0]);
                    }
                }
            }

        }
        System.out.println(dp[n]);

    }

}