前言
应广大同学要求，开始以OD机考题作为练习题，看看算法和数据结构掌握情况。有需要练习的可以关注下。此题难度略大，需要对背包问题较为熟悉，同时题干信息量较大，都为解题造成了一定难度。
在开始此题前请提前查看Java数据结构与算法(0/1背包问题)-CSDN博客，否则理解有些困难。
描述
王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：
| 主件 | 附件 |
| 电脑 | 打印机，扫描仪 |
| 书柜 | 图书 |
| 书桌 | 台灯，文具 |
| 工作椅 | 无 |
如果要买归类为附件的物品，必须先买该附件所属的主件，且每件物品只能购买一次。
每个主件可以有 0 个、 1 个或 2 个附件。附件不再有从属于自己的附件。
王强查到了每件物品的价格（都是 10 元的整数倍），而他只有 N 元的预算。除此之外，他给每件物品规定了一个重要度，用整数 1 ~ 5 表示。他希望在花费不超过 N 元的前提下，使自己的满意度达到最大。
满意度是指所购买的每件物品的价格与重要度的乘积的总和，假设设第𝑖i件物品的价格为𝑣[𝑖]v[i]，重要度为𝑤[𝑖]w[i]，共选中了𝑘k件物品，编号依次为𝑗1,𝑗2,...,𝑗𝑘j1,j2,...,jk，则满意度为：𝑣[𝑗1]∗𝑤[𝑗1]+𝑣[𝑗2]∗𝑤[𝑗2]+…+𝑣[𝑗𝑘]∗𝑤[𝑗𝑘]v[j1]∗w[j1]+v[j2]∗w[j2]+…+v[jk]∗w[jk]。（其中 * 为乘号）
请你帮助王强计算可获得的最大的满意度。
输入描述：
输入的第 1 行，为两个正整数N，m，用一个空格隔开：
（其中 N （ N<32000 ）表示总钱数， m （m <60 ）为可购买的物品的个数。）
从第 2 行到第 m+1 行，第 j 行给出了编号为 j-1 的物品的基本数据，每行有 3 个非负整数 v p q
（其中 v 表示该物品的价格（ v<10000 ）， p 表示该物品的重要度（ 1 ~ 5 ）， q 表示该物品是主件还是附件。如果 q=0 ，表示该物品为主件，如果 q>0 ，表示该物品为附件， q 是所属主件的编号）
输出描述：
输出一个正整数，为张强可以获得的最大的满意度。
输入：
1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0输出：
2200
实现原理
本题是0/1背包问题的升级版，0/1背包问题只考虑是否买当前物品。本题则需要考虑多种情况。
不买主件、买主件、买主件和附件一、买主件和附件二、买主件和附件一附件二等5种情况。
前置的构建二维数组比较关键。题干中的每个主件可以有 0 个、 1 个或 2 个附件。附件不再有从属于自己的附件是关键信息。
实现代码
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
int res = 0;
String str = scanner.nextLine();
String[] numStr = str.split(" ");
int N = Integer.valueOf(numStr[0]);
int m = Integer.valueOf(numStr[1]);
int[][] v = new int[m + 1][3];
int[][] w = new int[m + 1][3];
for (int i = 1; i <= m; i++) {
int v_t, p_t, q_t;
String[] tempStr = scanner.nextLine().split(" ");
v_t = Integer.valueOf(tempStr[0]);
p_t = Integer.valueOf(tempStr[1]);
q_t = Integer.valueOf(tempStr[2]);
if (q_t == 0) {
//主件
v[i][0] = v_t;
w[i][0] = p_t * v_t;
} else if (v[q_t][1] == 0) {
//附件一
v[q_t][1] = v_t;
w[q_t][1] = p_t * v_t;
} else {
//附件二
v[q_t][2] = v_t;
w[q_t][2] = p_t * v_t;
}
}
int[][] dp = new int[m + 1][N + 1];
for (int i = 1; i < m + 1; i++) {// 遍历物品
for (int j = 1; j < N + 1; j++) { // 遍历背包
if (v[i][0] > j) {
dp[i][j] = dp[i - 1][j]; // 都不买
} else {
if (v[i][0] <= j) { // 只买主件
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - v[i][0]] + w[i][0]);
}
if (v[i][0] + v[i][1] <= j) { // 买主件+附件1
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v[i][0] - v[i][1]] + w[i][0] + w[i][1]);
}
if (v[i][0] + v[i][2] <= j) { // 买主件+附件2
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v[i][0] - v[i][2]] + w[i][0] + w[i][2]);
}
if (v[i][0] + v[i][1] + v[i][2] <= j) { // 买主件+附件1+附件2
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v[i][0] - v[i][1] - v[i][2]] + w[i][0] + w[i][1] + w[i][2]);
}
}
}
}
System.out.println(dp[m][N]);
}
}
