题解 | #购物单# java

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int money = sc.nextInt(); // 总钱数
        int n = sc.nextInt(); // 商品数
        Map<Integer, Product> productMap = new HashMap<>();
        int[][] arr = new int[n][3];
        for (int i = 0; i < n; i++) {
            int v = sc.nextInt();
            int p = sc.nextInt();
            int q = sc.nextInt();
            arr[i][0] = v; // 价格
            arr[i][1] = p; // 重要度
            arr[i][2] = q; // 标识
            if (q == 0) {
                productMap.put(i + 1, new Product(v, p));
            }
        }
        for (int[] ints : arr) {
            int index = ints[2];
            if (index != 0) {
                int count = productMap.get(index).count++;
                if (count == 1) {
                    productMap.get(index).firstPrice = ints[0];
                    productMap.get(index).firstValue = ints[1];
                } else {
                    productMap.get(index).secondPrice = ints[0];
                    productMap.get(index).secondValue = ints[1];
                }
            }
        }
        Product[] products = new Product[productMap.size()];
        int index = 0;
        for (Integer integer : productMap.keySet()) {
            products[index++] = productMap.get(integer);
        }

        int[] dp = new int[money + 1];


        for (int i = 0; i < products.length; i++) { // 物品
            Product product = products[i];
            for (int j = money; j >= product.price; j--) { // B背包
                dp[j] = Math.max(dp[j], dp[j - product.price] + product.price *
                                 product.value); // 主件单独
                if (product.count >= 1) {
                    if (j >= product.price + product.firstPrice) {
                        dp[j] = Math.max(dp[j], dp[j - product.price - product.firstPrice] +
                                         product.price * product.value + product.firstPrice * product.firstValue);
                    }
                    if (j >= product.price + product.secondPrice) {
                        dp[j] = Math.max(dp[j], dp[j - product.price - product.secondPrice] +
                                         product.price * product.value + product.secondPrice * product.secondValue);
                    }
                }
                if (product.count == 2 &&
                        j >= product.price + product.firstPrice + product.secondPrice) {
                    dp[j] = Math.max(dp[j], dp[j - product.price - product.firstPrice -
                                               product.secondPrice] +
                                     product.price * product.value + product.firstPrice * product.firstValue +
                                     product.secondPrice * product.secondValue);
                }
            }
        }

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

class Product {
    public int count; // 附件的个数
    public int price; // 主件价格
    public int value; // 主件重要度
    public int firstPrice; // 附件1价格
    public int firstValue; // 附件1重要度
    public int secondPrice; // 附件2价格
    public int secondValue; // 附件2重要度

    public Product(int price, int value) {
        this.price = price;
        this.value = value;
    }
}