题解 | #购物单#

本题难点

1. 确定好元素到底是什么，比如附件总是与主件同时出现。
2. 清晰的确定出所有的状态，每一组状态包括：主件，主件+附件1，主件+附件2，主件+附件1+附件2。
3. 确定状态之间的关系，因为这四个状态是互斥，决定了本问题是分组背包。(由于一开始我没有找出最后一种状态，一直以为这是01背包问题，浪费了很长时间来找状态）

Java代码实现

参考了别的题解的思路，给出了优化版本的分组背包的代码，只用一维数组。本代码可以直接运行，12组数据都已通过。

import java.util.Arrays;
import java.util.Scanner;

/**
 * --------------------------------------------
 * FileName:     购物单02
 * CreateBy:     IntelliJ IDEA
 * Author:       ffforest2012
 * Date:         2023-04-12
 * Description : 正确解法，分组背包
 * --------------------------------------------
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();// 总体积-总钱数
        int n = sc.nextInt();// 物品个数，这里的物品比较特殊，包含了主件和附件
        boolean[] once = new boolean[n + 1];// 某个组件是否已经有一个附件
        boolean[] isPar = new boolean[n + 1];// 某个组件是否是主件
        int[][] w = new int[n + 1][4];// 每个物品的真实价格-附件的要加上主件的价格
        int[][] v = new int[n + 1][4];// 每个物品的真实满意度-附件的要加上主件的满意度 满意度=价格*重要度=a*b
        int[] nums = new int[n + 1];// 每个物品有多少件，包括主件，主件+附件1，主件+附件2，主件+附件1+附件2
        Arrays.fill(nums, 1);// 默认主件都有1件
        int[] f = new int[m + 1];


        for (int i = 1; i <= n; i++) {
            int a = sc.nextInt();// 价格
            int b = sc.nextInt();// 重要度
            int c = sc.nextInt();// 是否主件
            if (c == 0) {
                isPar[i] = true;
                for (int j = 0; j < 4; j++) {
                    w[i][j] += a;
                    v[i][j] += a * b;
                }
            } else {// c是i物品的主件
                if (!once[c]) {// 主件还没有附件，将第一个附件添加到1号位置
                    once[c] = true;
                    w[c][1] += a;
                    v[c][1] += a * b;
                    nums[c] = 2;
                } else {// 主件已经有一个附件，将第二个附件添加到2号位置，同时，将3号位置放入全部
                    w[c][2] += a;
                    v[c][2] += a * b;
                    w[c][3] = w[c][1] + a;
                    v[c][3] = v[c][1] + a * b;
                    nums[c] = 4;
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            if (!isPar[i]) continue;
            for (int j = m; j >= 0; j--) {
                for (int k = 0; k < nums[i]; k++) {
                    if (j >= w[i][k]) {
                        f[j] = Math.max(f[j], f[j - w[i][k]] + v[i][k]);
                    }
                }
            }
        }
        System.out.println(f[m]);

    }
}