| 主件 | 附件 |
| 电脑 | 打印机，扫描仪 |
| 书柜 | 图书 |
| 书桌 | 台灯，文具 |
| 工作椅 | 无 |
输入的第 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
50 5 20 3 5 20 3 5 10 3 0 10 2 0 10 1 0
130
由第1行可知总钱数N为50以及希望购买的物品个数m为5； 第2和第3行的q为5，说明它们都是编号为5的物品的附件； 第4~6行的q都为0，说明它们都是主件，它们的编号依次为3~5； 所以物品的价格与重要度乘积的总和的最大值为10*1+20*3+20*3=130
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int m = in.nextInt();
int[] v = new int[m + 1]; //价格
int[] p = new int[m + 1]; //重要度
int[] q = new int[m + 1]; //所属主件编号
for (int i = 1 ; i 1 ; i++) {
v[i] = in.nextInt();
p[i] = in.nextInt();
q[i] = in.nextInt();
}
System.out.println(getMaxSat(v, p, q, N, m));
}
//获取最大满意值方法
public static int getMaxSat(int[] v, int[] p, int[] q, int N, int m) {
Good[][] good = new Good[m + 1][3]; //g[i][j]表示i号物品的第j个附件（最多2个），i=0表示i号商品是主件，g[i][0]为空表示i号商品为附件
int max = 0;
int[] sat = new int [N + 1]; //sat[i]表示花费i元时的满意度
//跟据条件初始化good对象数组
for (int i = 1 ; i <= m ; i++) {
Good gt = new Good(v[i], v[i] * p[i]);
if (q[i] == 0) {
good[i][0] = gt;
} else { //是附件时判断是否存在另一个附件
if (good[q[i]][1] == null)
good[q[i]][1] = gt;
else
good[q[i]][2] = gt;
}
}
for (int i = 1; i <= m; i++) {
for (int j = N; j >= 0; j--) {
Good gt0 = good[i][0];
Good gt1 = good[i][1];
Good gt2 = good[i][2];
// i号商品不是主件时跳过循环
if (gt0 == null)
break;
// 第i号物品为主件时列出四种情况：主，主+附1，主+附2，主+附1+附2，并记录四种情况下的最大的满意度
else {
//该主件没有附件
if (gt1 == null && gt2 == null) {
if (gt0.v <= j) {
//和原来的sat[j]比较，取最大满意度并记录
sat[j] = Math.max(sat[j], gt0.vp + sat[j - gt0.v]);
}
}
//该主件有1个附件，若剩余金额允许购买主件和附件，比较主和主+附1的最大满意度
if (gt1 != null) {
if (gt0.v <= j) {
sat[j] = Math.max(sat[j], gt0.vp + sat[j - gt0.v]);
}
if (gt0.v + gt1.v <= j) {
sat[j] = Math.max(sat[j], gt0.vp + gt1.vp + sat[j - gt0.v - gt1.v]);
}
}
//该主件有2个附件，若剩余金额允许购买主件和附件，比较主，主+附1，主+附2，主+附1+附2的最大满意度
if (gt2 != null) {
if (gt0.v <= j) {
sat[j] = Math.max(sat[j], gt0.vp + sat[j - gt0.v]);
}
if (gt0.v + gt1.v <= j) {
sat[j] = Math.max(sat[j], gt0.vp + gt1.vp + sat[j - gt0.v - gt1.v]);
}
if (gt0.v + gt2.v <= j) {
sat[j] = Math.max(sat[j], gt0.vp + gt2.vp + sat[j - gt0.v - gt2.v]);
}
if (gt0.v + gt1.v + gt2.v <= j) {
sat[j] = Math.max(sat[j], gt0.vp + gt1.vp + gt2.vp + sat[j - gt0.v - gt1.v - gt2.v]);
}
}
}
}
}
return sat[N];
} }
//定义商品类
class Good {
int v;//价格
int vp;//满意度
public Good(int v, int vp) {
this.v = v;
this.vp = vp;
} }
import java.util.ArrayList;
import java.util.List;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.concurrent.ConcurrentHashMap;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer line = new StringTokenizer(br.readLine());
int money = Integer.parseInt(line.nextToken());
int num = Integer.parseInt(line.nextToken());
Good[] goods = new Good[num];
int i = 0;
while (i < num) {
line = new StringTokenizer(br.readLine());
int v = Integer.valueOf(line.nextToken());
int p = Integer.valueOf(line.nextToken());
int q = Integer.valueOf(line.nextToken());
if (goods[i] == null) {
goods[i] = new Good(v, p, q);
} else {
goods[i].v = v;
goods[i].p = p;
goods[i].q = q;
}
if (q > 0) { // 附件
if (goods[q - 1] == null) { // 主件还未创建
goods[q - 1] = new Good(0, 0, 0);
}
if (goods[q - 1].g1 < 0) {
goods[q - 1].g1 = i;
} else {
goods[q - 1].g2 = i;
}
}
i++;
}
System.out.println(shopping(goods, money));
}
public static int shopping(Good[] goods, int money) {
int dp[] = new int[money + 1];
for (int i = 0; i < goods.length; i++) {
Good g = goods[i];
for (int j = money; j >= g.v && g.q == 0; j--) {
// 只买主件
dp[j] = Math.max(dp[j - g.v] + g.p * g.v, dp[j]);
// 主 + 附1
if (g.g1 >= 0 && j >= (g.v + goods[g.g1].v)) {
Good g1 = goods[g.g1];
dp[j] = Math.max(dp[j - g.v - g1.v] + g.p * g.v + g1.v * g1.p, dp[j]);
}
// 主 + 附2
if (g.g2 >= 0 && j >= (g.v + goods[g.g2].v)) {
Good g2 = goods[g.g2];
dp[j] = Math.max(dp[j - g.v - g2.v] + g.p * g.v + g2.v * g2.p, dp[j]);
}
// 主 + 附1 + 附2
if (g.g1 >= 0 && g.g2 >= 0 && j >= (g.v + goods[g.g1].v + goods[g.g2].v)) {
Good g1 = goods[g.g1];
Good g2 = goods[g.g2];
dp[j] = Math.max(dp[j - g.v - g1.v - g2.v] + g.p * g.v + g1.v * g1.p + g2.v *
g2.p, dp[j]);
}
}
}
return dp[money];
}
public static class Good {
private int v; // 价格
private int p; // 重要性
private int q; // 主件id
private int g1 = -1; // 附件1
private int g2 = -1; // 附件2
public Good(int v, int p, int q) {
this.v = v;
this.p = p;
this.q = q;
}
}
} 
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int m = in.nextInt() / 10;
int s = in.nextInt();
//最大数组长度
Good[] gs = new Good[s];
//组装基础数据
for (int i = 0; i < s ; i++) {
int v = in.nextInt() / 10;
int p = in.nextInt();
int q = in.nextInt();
//生成对象并按照顺序写入
gs[i] = new Good(v, p * v, q);
}
//二次循环写入附件信息
for (int i = 0; i < s ; i++) {
Good good = gs[i];
if (!good.isMain) {
Good parent = gs[good.q - 1];
if (parent.q1 == -1) {
parent.q1 = i;
} else {
parent.q2 = i;
}
}
}
//结果集分值，物品
int[][] res = new int[m + 1][s + 1];
//一次循环物品
for (int i = 1; i < s + 1 ; i++) {
//二次循环商品价值
for (int j = 0; j <= m ; j++) {
Good good = gs[i - 1];
//附件数据忽略，取上一个物品的值
if (!good.isMain) {
res[j][i] = res[j][i - 1];
} else {
//赋默认值，上一个物品当前分值最优解
res[j][i] = res[j][i - 1];
//主物品剩余分值优解
if (good.v <= j) {
res[j][i] = Math.max(res[j][i], good.p + res[j - good.v][i - 1]);
}
//主物品+q1+剩余分值最优解
if (good.q1 > -1 && good.v + gs[good.q1].v <= j) {
int count = good.p + gs[good.q1].p + res[j - good.v - gs[good.q1].v][i - 1];
res[j][i] = Math.max(res[j][i], count);
}
//主物品+q2+剩余物品最优解
if (good.q2 > -1 && good.v + gs[good.q2].v <= j) {
int count = good.p + gs[good.q2].p + res[j - good.v - gs[good.q2].v][i - 1];
res[j][i] = Math.max(res[j][i], count);
}
//主物品+两附件+剩余物品最优解
if (good.q1 > -1 && good.q2 > -1 &&
good.v + gs[good.q1].v + gs[good.q2].v <= j) {
int count = good.p + gs[good.q1].p + gs[good.q2].p + res[j - good.v -
gs[good.q1].v - gs[good.q2].v][i - 1];
res[j][i] = Math.max(res[j][i], count);
}
}
}
}
//输出结果
System.out.println(res[m][s] * 10);
}
//商品对象
static class Good {
//商品价值
public int v;
//计算后的满意度
public int p;
//是否为附件
public int q;
//是否主件，默认不是
public boolean isMain = false;
//附件编号
public int q1 = -1;
public int q2 = -1;
public Good(int v, int p, int q) {
this.v = v;
this.p = p;
this.q = q;
//提前判断好是否是主件
if (q == 0) {
this.isMain = true;
}
}
}
}
我看过很多人写的代码，他们在“dp[i][j] = dp[i-1][j]”这里的处理都显得没有逻辑可言，下面的四个max判断大部分人第一条写的Math.max(dp[i][j],dp[i-1][j-v] + tempdp);,这样写逻辑根本无法自洽，同01背包问题分析，第一次如果你不买那么就是dp[i-1][j],买了就是dp[i-1][j-v] + tempdp，不存在说不买还是dp[i][j]的。 往下三条if这里之所以写dp[i][j]是因为它是同上一条计算出来的dp[i][j]的比较，是不同购买方案的比较。只要这里能理解透彻，我觉得这题大家就能懂了， 希望我下面代码对大家有所帮助。 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int money = sc.nextInt(); int n = sc.nextInt(); if (n <= 0 || money <= 0) System.out.println(0); good[] Gs = new good[n + 1]; for (int i = 1; i <= n; i++) { int v = sc.nextInt();//物品价格 int p = sc.nextInt();//物品重要度 int q = sc.nextInt();//是否主件（主件编号） Gs[i] = new good(v, p, q); } for (int i = 1; i <= n; i++) { if (Gs[i] != null && Gs[i].q > 0) { //如果是附件，则给附件ID置位，方便后面计算附件方案 if (Gs[Gs[i].q].a1 == 0) { Gs[Gs[i].q].setA1(i); } else if (Gs[Gs[i].q].a2 == 0){ Gs[Gs[i].q].setA2(i); } } } int[][] dp = new int[n + 1][money + 1]; for (int i = 1; i <= n; i++) { int v = 0, v1 = 0, v2 = 0, v3 = 0, tempdp = 0, tempdp1 = 0, tempdp2 = 0, tempdp3 = 0; //只有主件 v = Gs[i].v; tempdp = Gs[i].p * v; //主件加附件1 if(Gs[i].a1 != 0){ v1 = Gs[Gs[i].a1].v + v; tempdp1 = tempdp + Gs[Gs[i].a1].v * Gs[Gs[i].a1].p; } //主件加附件2 if(Gs[i].a2 != 0){ v2 = Gs[Gs[i].a2].v + v; tempdp2 = tempdp + Gs[Gs[i].a2].v * Gs[Gs[i].a2].p; } //主件加附件1和附件2 if(Gs[i].a1 != 0 && Gs[i].a2 != 0){ v3 = Gs[Gs[i].a1].v + Gs[Gs[i].a2].v + v; tempdp3 = tempdp + Gs[Gs[i].a1].v * Gs[Gs[i].a1].p + Gs[Gs[i].a2].v * Gs[Gs[i].a2].p; } for(int j = 1; j <= money; j++){ if(Gs[i].q > 0) dp[i][j] = dp[i-1][j];//如果物品是附件，先不买 else if(Gs[i].q == 0){ dp[i][j] = j >= v? Math.max(dp[i-1][j],dp[i-1][j-v] + tempdp) : dp[i-1][j]; //Math.max(不买，买) : 钱不够 dp[i][j] = j >= v1? Math.max(dp[i][j],dp[i-1][j-v1] + tempdp1) : dp[i][j]; //此处dp[i][j]指的是上一行的dp[i][j],即比较不同购买方案,往下的dp[i][j]的值一直是被不断刷新的 dp[i][j] = j >= v2? Math.max(dp[i][j],dp[i-1][j-v2] + tempdp2) : dp[i][j]; dp[i][j] = j >= v3? Math.max(dp[i][j],dp[i-1][j-v3] + tempdp3) : dp[i][j]; } } } System.out.println(dp[n][money]); } /** * 定义物品类 */ private static class good { public int v; //物品的价格 public int p; //物品的重要度 public int q; //物品的主附件ID public int a1=0; //附件1ID public int a2=0; //附件2ID public good(int v, int p, int q) { this.v = v; this.p = p; this.q = q; } public void setA1(int a1) { this.a1 = a1; } public void setA2(int a2) { this.a2 = a2; } } }
import java.util.Scanner;
public class HJ16 {
/**
* 【购物单】
* <p>
* 描述：王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的
* 必须先买该附件所属的主件，且每件物品只能购买一次
* 每件物品规定了一个重要度，用整数 1 ~ 5 表示
* <p>
* 要求：希望在花费不超过 N 元的前提下，使自己的满意度达到最大
* <p>
* 【解题思路】：1.创建物品属性类v-价格，p-重要度，q-主件或附件（0或主件编号）
* 2.将输入信息放入物品类
* 3.分四种，主件，主件+附件1，主件+附件2，主件+附件1+附件2，逐次算出满意度。
* 4.遍历这四种情况下的最优解，合并最优解。
*/
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 输入
int totalMoney = sc.nextInt();//总钱数
int goodNumber = sc.nextInt();//物品个数
Good[] goodArray = new Good[goodNumber + 1];
for (int i = 1; i <= goodNumber; i++) {
Good good = goodArray[i];
if (good == null) {
good = new Good();
}
good.setV(sc.nextInt());
good.setP(sc.nextInt());
good.setQ(sc.nextInt());
if (good.getQ() > 0) {
if (goodArray[good.getQ()] == null) {
goodArray[good.getQ()] = new Good();
}
//给主件赋值附件信息
if (goodArray[good.getQ()].getAttach1() == null) {
goodArray[good.getQ()].setAttach1(good);
} else {
goodArray[good.getQ()].setAttach2(good);
}
}
goodArray[i] = good;
}
int[][] dp = new int[goodNumber + 1][totalMoney + 1];//最终的满意度
dp[0][0] = 0;
//每种情况的满意度数组
int[][] level = new int[goodNumber + 1][4];
int[][] costMoney = new int[goodNumber + 1][4];
for (int i = 1; i <= goodNumber; i++) {
Good g = goodArray[i];
//只有主件
level[i][0] = g.getV() * g.getP();
costMoney[i][0] = g.getV();
//附件1
if (g.getAttach1() != null ) {
level[i][1] = g.getV() * g.getP() + g.getAttach1().getV() * g.getAttach1().getP();
costMoney[i][1] = g.getV() + g.getAttach1().getV();
}
//附件2
if (g.getAttach2() != null) {
level[i][2] = g.getV() * g.getP() + g.getAttach2().getV() * g.getAttach2().getP();
costMoney[i][2] = g.getV() + g.getAttach2().getV();
}
//附件1+附件2
if (g.getAttach1() != null && g.getAttach2() != null) {
level[i][3] = g.getV() * g.getP() + g.getAttach1().getV() * g.getAttach1().getP() +
g.getAttach2().getV() * g.getAttach2().getP();
costMoney[i][3] = g.getV() + g.getAttach1().getV() + g.getAttach2().getV();
}
for (int j = totalMoney; j >= 0; j = j - 10) {
for (int k = 0; k < costMoney[i].length; k++) {
if (g.getQ() > 0) {
dp[i][j] = dp[i - 1][j];
} else {
if (costMoney[i][k] <= j) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - costMoney[i][k]] + level[i][k]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
}
}
System.out.println(dp[goodNumber][totalMoney]);
}
}
class Good {
private int v;//价格
private int p;//重要度
private int q;//主件or附件
private Good attach1;//附件1
private Good attach2;//附件2
public int getV() {
return v;
}
public void setV(int v) {
this.v = v;
}
public int getP() {
return p;
}
public void setP(int p) {
this.p = p;
}
public int getQ() {
return q;
}
public void setQ(int q) {
this.q = q;
}
public Good getAttach1() {
return attach1;
}
public void setAttach1(Good attach1) {
this.attach1 = attach1;
}
public Good getAttach2() {
return attach2;
}
public void setAttach2(Good attach2) {
this.attach2 = attach2;
}
} 
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;
public class T16 {
static int maxsumOfSatisfaction = 0;
public static void main(String[] args) {
HashMap<Integer, int[]> goods = new HashMap<>();
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
String[] split = str.split(" ");
int money = Integer.parseInt(split[0]);
int number = Integer.parseInt(split[1]);
for (int i = 0; i < number; i++) {
String temp = sc.nextLine();
int[] detail = new int[3];
String[] split1 = temp.split(" ");
detail[0] = Integer.parseInt(split1[0]);
detail[1] = Integer.parseInt(split1[1]);
detail[2] = Integer.parseInt(split1[2]);
goods.put(i, detail);
}
orderByMo(goods);
getAllCase(0, goods, new ArrayList<>(), money, 0, 0);
System.out.println(maxsumOfSatisfaction);
}
private static void orderByMo(HashMap<Integer, int[]> goods) {
for (int i = 0; i < goods.size(); i++) {
int[] good = goods.get(i);
if (good[2] > i && good[2] != 0) {
//交换主件和附件的位置
goods.put(i, goods.get(good[2] - 1));
goods.put(good[2] - 1, good);
//修改附件信息
for (int j = i + 1; j < goods.size(); j++) {
int[] ints = goods.get(j);
if (ints[2] == good[2]) {
ints[2] = i + 1;
goods.put(j, ints);
}
}
}
}
}
public static void getAllCase(int index, HashMap<Integer, int[]> goods, ArrayList<Integer> tempCase, int money, int sum, int sumOfSatisfaction) {
if (sum > money) {
return;
}
ArrayList<Integer> copy = new ArrayList<>(tempCase);
if (index == goods.size()) {
if (tempCase.size() != 0) {
if (sumOfSatisfaction > maxsumOfSatisfaction) {
maxsumOfSatisfaction = sumOfSatisfaction;
}
}
} else {
//选择购买这个商品
int[] good = goods.get(index);
sum += good[0];
if (good[2] == 0) {
tempCase.add(index);
getAllCase(index + 1, goods, tempCase, money, sum, sumOfSatisfaction + good[0] * good[1]);
} else {
if (tempCase.contains(good[2] - 1)) {
tempCase.add(index);
getAllCase(index + 1, goods, tempCase, money, sum, sumOfSatisfaction + good[0] * good[1]);
}
}
//选择不购买这个商品
getAllCase(index + 1, goods, copy, money, sum - good[0], sumOfSatisfaction);
}
}
} 
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]);
}
}
先参考了一下评论区的思想，就是分成了不选择附件、选择一个附件、选择两个附件三种情况，独立写出😅。100%通过率
import java.util.Scanner;
public class Main {
public static class MainItem{
public int price;
public int weights;
public int[][] subItems;
int x;
public MainItem(){
x=0;
subItems=new int[2][2]; //最多两个物品，有两个属性，price，weights
}
public void serMainItem(int[] info){
price=info[0];
weights=info[1];
}
public void addSubItem(int[] info){
subItems[x][0]=info[0];
subItems[x][1]=info[1];
x++;
}
public void output(){
System.out.println(price+" "+weights);
for(int i=0;i<x;i++){
System.out.println(subItems[i][0]+" "+subItems[i][1]);
}
System.out.println("");
}
public int[][] cosAndSas(){ //最多4种情况，买0，买0 1，买0 2，买0 1 2
//数组长度有1,2,4 三种情况
int n=x+1;
if(x==2){
n=4;
}
int[][] result=new int[n][2];
//主件
result[0][0]=price;
result[0][1]=price*weights;
if(x>0){
//附件1
result[1][0]=price+subItems[0][0];
result[1][1]=result[0][1]+subItems[0][0]*subItems[0][1];
}
if(x>1){
//附件2
result[2][0]=price+subItems[1][0];
result[2][1]=result[0][1]+subItems[1][0]*subItems[1][1];
//所有附件
result[3][0]=price+subItems[0][0]+subItems[1][0];
result[3][1]=-result[0][1]+result[1][1]+result[2][1];
}
return result;
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 处理输入,m件物品, 编号i对应数组下标i-1 关键问题：主件可能排在副件后面，使用递归时可以使用map操作
//DP时可将附件作为考虑主件时的子问题处理，由于该问题主件最多2个附件，此时最好新建类，将附件加入主件的属性
int N=in.nextInt(); //输入m N
int m=in.nextInt();
in.nextLine();
int mainItemNumber=0;
int[][] items=new int[m][3];
int[] mark=new int[m+1]; //主件id对应mainItem数组下标的map
for(int i=0;i<m;i++){
for(int j=0;j<3;j++){
items[i][j]=in.nextInt();
}
if(items[i][2]==0){//主件 i=id-1
mark[i+1]=mainItemNumber++; //记录主件在mainItem的index并更新主件数量
}
}
MainItem[] mainItems=new MainItem[mainItemNumber];
for(int i=0;i<mainItemNumber;i++){
mainItems[i]=new MainItem();
}
int index=0;
for(int i=0;i<m;i++){
if(items[i][2]==0){ //主件 更新主件数组信息 并更新主件index
mainItems[index++].serMainItem(items[i]);
}else{ //附件 添加信息到主件
mainItems[mark[items[i][2]]].addSubItem(items[i]);
}
}
int[][] DP=new int[mainItemNumber+1][N/10+1]; //创建DP数组,DP[i][j] 代表处理到第i件物品花最多j的钱获得的最大满意度
//复杂度 M*M*N*4约为O(N*m^2)
for(int i=1;i<=mainItemNumber;i++){ //从第1个物品开始，第0个代表没有物品状态，默认是0无须修改
for(int j=0;j<i;j++){// 向前看所有的情况更新当前的状态
for(int k=1;k<=N/10;k++){//从花10元开始，花0元默认是0满意度 无须修改
//不买第i件物品
DP[i][k]=Math.max(DP[i][k],DP[j][k]);
//买第i件物品并考虑附件
int[][] cosAndSas=mainItems[i-1].cosAndSas();
for(int l=0;l<cosAndSas.length;l++){
int jk=k-cosAndSas[l][0]/10;
if(jk>=0){
DP[i][k]=Math.max(DP[i][k],DP[j][jk]+cosAndSas[l][1]);
}
}
}
}
}
System.out.println(DP[mainItemNumber][N/10]);
}
} 有没有大佬帮忙看看我这个用例为什么是7400而不是7430，实在找不到问题了 用例： 2000 10 500 1 0 400 4 0 300 5 1 400 5 1 200 5 0 500 4 5 400 4 0 320 2 0 410 3 0 400 3 5 代码：package com.learn.java.huawei; import lombok.Data; import java.util.*; import java.util.stream.Collectors; /** * <p> * <a href = "https://juejin.cn/post/6844903541522333704">购物单</a> * </p> * * @author Caoyuewen 2023/5/9 */ public class ShopList2 { // <id,good> private static final TreeMap<Integer, Good> indexGoodMap = new TreeMap<>(); public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); // 总金额 int m = in.nextInt(); // 物品数 for (int i = 1; i <= m; i++) { Good good = new Good(); good.setId(i); good.setPrice(in.nextInt()); // 价格 good.setWeight(in.nextInt()); // 重要度 good.setParentId(in.nextInt()); // 是否附件,主件0,附件:主件id indexGoodMap.put(i, good); } // 初始化主件附件关系 indexGoodMap.values().forEach(good -> { if (good.getParentId() != 0) { Good parent = indexGoodMap.get(good.getParentId()); if (parent.getAttach1() == null) { parent.setAttach1(good); } else { parent.setAttach2(good); } } }); printGoods(new ArrayList<>(indexGoodMap.values())); System.out.println(maxHappiness(n)); } private static int maxHappiness(int N) { List<Good> parents = indexGoodMap.values().stream().filter(good -> good.getParentId() == 0).collect(Collectors.toList()); printGoods(parents); int size = parents.size(); int[][] dp = new int[size + 1][N + 1]; for (int[] ints : dp) { Arrays.fill(ints, 0); } // dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i][k]]+v[i][k]) // dp[i][j] = max(物品不放入背包, 主件 + 附件1, 主件 + 附件2, 主件 + 附件1 + 附件2) for (int i = 1; i <= size; i++) { Good good = parents.get(i - 1); for (int j = 0; j <= N; j += 10) { int h0, h1, h2, h3; // 主件 if (j >= good.getPrice(0)) { h0 = good.getHappiness(0); } else { dp[i][j] = dp[i - 1][j]; continue; } // 主件 + 附件1 if (good.getAttach1() != null && j >= good.getPrice(1)) { h1 = good.getHappiness(1); } else { h1 = 0; } // 主件 + 附件2 if (good.getAttach2() != null && j >= good.getPrice(2)) { h2 = good.getHappiness(2); } else { h2 = 0; } // 主件 + 附件1 + 附件2 if (good.getAttach1() != null && good.getAttach2() != null && j >= good.getPrice(3)) { h3 = good.getHappiness(3); } else { h3 = 0; } Result result = max(h0, h1, h2, h3); int cost = good.getPrice(result.getKind()); dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - cost] + result.getMaxHappiness()); } } printDp(dp); return dp[size][N]; } public static void printDp(int[][] dp) { for (int[] ints : dp) { for (int i = 0; i < ints.length; i++) { if (ints[i] != 0) { System.out.print(i + ": " + ints[i] + " "); } } System.out.println(); } } public static void printGoods(List<Good> goods) { goods.forEach(v -> System.out.println(v.toString())); } public static Result max(int... nums) { Result result = new Result(); int max = nums[0]; result.setKind(0); for (int i = 0; i < nums.length; i++) { if (nums[i] > max) { max = nums[i]; result.setKind(i); } } result.setMaxHappiness(max); return result; } private static class Good { private int id; private int price; private int weight; private int parentId; // 附件1 private Good attach1; // 附件2 private Good attach2; private int status = 0; // 1.已买 0.未买 /** * 0:主件 * 1:主件+附件1 * 2:主件+附件2 * 3:主件+附件1 + 附件2 */ public int getPrice(int attachNum) { if (attachNum == 0) { return price; } else if (attachNum == 1 && attach1 != null) { return price + attach1.getPrice(); } else if (attachNum == 2 && attach2 != null) { return price + attach2.getPrice(); } else if (attachNum >= 3 && attach1 != null && attach2 != null) { return price + attach1.getPrice() + attach2.getPrice(); } else { return price; } } /** * 0:主件 * 1:主件+附件1 * 2:主件+附件2 * 3:主件+附件1 + 附件2 */ public int getHappiness(int attachNum) { if (attachNum == 0) { return price * weight; } else if (attachNum == 1 && attach1 != null) { return (price * weight) + (attach1.getWeight() * attach1.getPrice()); } else if (attachNum == 2 && attach2 != null) { return (price * weight) + (attach2.getWeight() * attach2.getPrice()); } else if (attachNum >= 3 && attach1 != null && attach2 != null) { return (price * weight) + (attach1.getPrice() * attach1.getWeight()) + (attach2.getPrice() * attach2.getWeight()); } else { return price * weight; } } public int getId() { return id; } public void setId(int id) { this.id = id; } public int getPrice() { return price; } public void setPrice(int price) { this.price = price; } public int getWeight() { return weight; } public void setWeight(int weight) { this.weight = weight; } public int getParentId() { return parentId; } public void setParentId(int parentId) { this.parentId = parentId; } public Good getAttach1() { return attach1; } public void setAttach1(Good attach1) { this.attach1 = attach1; } public Good getAttach2() { return attach2; } public void setAttach2(Good attach2) { this.attach2 = attach2; } public int getStatus() { return status; } public void setStatus(int status) { this.status = status; } @Override public String toString() { return "Good{" + "id=" + id + ", price=" + price + ", weight=" + weight + ", parentId=" + parentId + ", attach1=" + attach1 + ", attach2=" + attach2 + ", status=" + status + '}'; } } public static class Result { private int maxHappiness; /** * 0:主件 * 1:主件+附件1 * 2:主件+附件2 * 3:主件+附件1 + 附件2 */ private int kind; public int getMaxHappiness() { return maxHappiness; } public void setMaxHappiness(int maxHappiness) { this.maxHappiness = maxHappiness; } public int getKind() { return kind; } public void setKind(int kind) { this.kind = kind; } } }
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); //总钱数
int m = sc.nextInt(); //可购买的物品数
Goods[] tab = new Goods[m + 1];
for (int i = 1; i < m + 1; i++) {
Goods gd = new Goods();
gd.setV(sc.nextInt());
gd.setP(sc.nextInt());
gd.setQ(sc.nextInt());
gd.setSat(gd.getP() * gd.getV());
tab[i] = gd;
}
for (int i = 1; i < m + 1; i++) {
if (tab[i].getQ() != 0) {
if (tab[tab[i].getQ()].getF1() != 0)
tab[tab[i].getQ()].setF2(i);
else
tab[tab[i].getQ()].setF1(i);
}
}
for (int i = 1; i < m + 1; i++) { //计算每个主件与附件的不同组合之后的价格与满意度
if (tab[i].getF1() != 0) {
tab[i].setV_f1(tab[i].getV() + tab[tab[i].getF1()].getV());
tab[i].setSat_f1(tab[i].getSat() + tab[tab[i].getF1()].getSat());
}
if (tab[i].getF2() != 0) {
tab[i].setV_f2(tab[i].getV() + tab[tab[i].getF2()].getV());
tab[i].setSat_f2(tab[i].getSat() + tab[tab[i].getF2()].getSat());
}
if (tab[i].getF1() != 0 && tab[i].getF2() != 0) {
tab[i].setV_all(tab[i].getV() + tab[tab[i].getF1()].getV() + tab[tab[i].getF2()].getV());
tab[i].setSat_all(tab[i].getSat() + tab[tab[i].getF1()].getSat() + tab[tab[i].getF2()].getSat());
}
}
int n = N / 10;
int[][] dp = new int[m + 1][n + 1]; //前i件商品在余额j的情况下的最大满意度
for (int i = 1; i < m + 1; i++) {
for (int j = n; j >= 1; j--) {
if (tab[i].q != 0) {
dp[i][j] = dp[i - 1][j];
} else {
if (tab[i].getF2() != 0 && (j * 10 >= tab[i].getV_all())) {
int tmp = Math.max(dp[i][j], dp[i - 1][(j * 10 - tab[i].getV_all()) / 10] + tab[i].getSat_all());
dp[i][j] = Math.max(dp[i - 1][j], tmp);
}
if (tab[i].getF2() != 0 && (j * 10 >= tab[i].getV_f2())) {
int tmp = Math.max(dp[i][j], dp[i - 1][(j * 10 - tab[i].getV_f2()) / 10] + tab[i].getSat_f2());
dp[i][j] = Math.max(dp[i - 1][j], tmp);
}
if (tab[i].getF1() != 0 && (j * 10 >= tab[i].getV_f1())) {
int tmp = Math.max(dp[i][j], dp[i - 1][(j * 10 - tab[i].getV_f1()) / 10] + tab[i].getSat_f1());
dp[i][j] = Math.max(dp[i - 1][j], tmp);
}
if (j * 10 >= tab[i].getV()) {
int tmp = Math.max(dp[i][j], dp[i - 1][(j * 10 - tab[i].getV()) / 10] + tab[i].getSat());
dp[i][j] = Math.max(dp[i - 1][j], tmp);
}else{
dp[i][j]=dp[i-1][j];
}
}
}
}
System.out.println(dp[m][n]);
}
}
class Goods { //商品类
int v; //商品价格
int p; //商品重要度：1-5
int q; //主件or附件：0-主件，其他-编号几的附件
int f1 = 0, f2 = 0; //最多有两个附件
int sat = 0; //物品本身的满意度
int sat_f1 = sat, sat_f2 = sat, sat_all = sat; //主件+附件一、主件+附件二、主件+两附件的满意度
int v_f1 = v, v_f2 = v, v_all = v; //主件+附件一、主件+附件二、主件+两附件的价格
public Goods() {
}
public int getV() {
return v;
}
public void setV(int v) {
this.v = v;
}
public int getP() {
return p;
}
public void setP(int p) {
this.p = p;
}
public int getQ() {
return q;
}
public void setQ(int q) {
this.q = q;
}
public void setF1(int f1) {
this.f1 = f1;
}
public void setF2(int f2) {
this.f2 = f2;
}
public int getF1() {
return f1;
}
public int getF2() {
return f2;
}
public int getSat() {
return sat;
}
public void setSat(int sat) {
this.sat = sat;
}
public int getSat_f1() {
return sat_f1;
}
public void setSat_f1(int sat_f1) {
this.sat_f1 = sat_f1;
}
public int getSat_f2() {
return sat_f2;
}
public void setSat_f2(int sat_f2) {
this.sat_f2 = sat_f2;
}
public int getSat_all() {
return sat_all;
}
public void setSat_all(int sat_all) {
this.sat_all = sat_all;
}
public int getV_f1() {
return v_f1;
}
public void setV_f1(int v_f1) {
this.v_f1 = v_f1;
}
public int getV_f2() {
return v_f2;
}
public void setV_f2(int v_f2) {
this.v_f2 = v_f2;
}
public int getV_all() {
return v_all;
}
public void setV_all(int v_all) {
this.v_all = v_all;
}
} 
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int money = in.nextInt();
int num = in.nextInt();
int count = 1;
//将主件、主附1、主附2、主附12分别存入4个位置中
int[][] value = new int[num + 1][4], point = new int[num + 1][4];
while (in.hasNextInt()) {
int v = in.nextInt();
int p = in.nextInt();
int q = in.nextInt();
if (q == 0) {
value[count][0] = v / 10;
point[count][0] = (v / 10) * p;
} else if (value[q][1] == 0) {
value[q][1] = v / 10;
point[q][1] = (v / 10) * p;
} else {
value[q][2] = v / 10;
point[q][2] = (v / 10) * p;
value[q][3] = value[q][2] + value[q][1];
point[q][3] = point[q][2] + point[q][1];
}
count++;
}
int[] dp = new int[(money / 10) + 1];
int len = money / 10;
int hp = 0;
//i：物品编号 j：金额 dp数组以金额为下标，记录当前金额能获得的最高分数
for (int i = 1; i <= num; i++) {
if (value[i][0] == 0) continue;
//允许主物件直接进入dp；附件只许在主物件基础上进入dp
for (int j = len; j >= value[i][0]; j--) {
//尝试放入主物件
if (j == value[i][0] || dp[j - value[i][0]] != 0) {
int tmp = dp[j - value[i][0]] + point[i][0];
//无论主物件目前是否比其他组合好，都先尝试在主物件基础上放副物件
for (int k = 1; k < 4; k++) {
if (value[i][k] == 0) break;
int nv = j + value[i][k];
int np = tmp + point[i][k];
if (nv < len && dp[nv] < np) {
dp[nv] = np;
hp = np > hp ? np : hp;
}
}
//在排查完主副组合后，将主物件单独的情况放入dp数组
dp[j] = tmp > dp[j] ? tmp : dp[j];
hp = tmp > hp ? tmp : hp;
}
}
}
System.out.println(hp * 10);
}
} 
import java.util.Scanner;
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
//结果只要求最大的状态值
static int maxStateValue = 0;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextLine()) {
String[] in1 = in.nextLine().split(" ");
int canUsedMoney = Integer.parseInt(in1[0]);
int goodsN = Integer.parseInt(in1[1]);
int[][] twoArr = new int[goodsN][4];
for (int i = 0; i < goodsN; i++) {
String[] temp = in.nextLine().split(" ");
int[] tempInt = new int[4];
for (int j = 0; j < temp.length; j++) {
tempInt[j] = Integer.parseInt(temp[j]);
}
tempInt[3] = i;
twoArr[i] = tempInt;
}
maxStateValue = 0;
dfs(twoArr, 0, new LinkedList<>(), canUsedMoney);
System.out.println(maxStateValue);
}
}
public static void dfs(int[][] twoArr, int start, LinkedList<int[]> track,
int canUsedMoney) {
//用来累计组合的钱
int countMoney = 0;
//用来累计状态的值
int stateValue = 0;
//多个附件的情况存储主件是否已经计算过
boolean[] used = new boolean[twoArr.length];
for (int i = 0; i < track.size(); i++) {
countMoney = countMoney + track.get(i)[0];
//当前那一个元素是否是附件,并且主件还未被计算过
if (track.get(i)[2] > 0 && !used[track.get(i)[2] - 1]) {
//是附件判断加上主件是否<=canUsedMoney
countMoney = countMoney + twoArr[track.get(i)[2] - 1][0];
if (countMoney <= canUsedMoney) {
//小于canUsedMoney就来计算结果
stateValue = stateValue + track.get(i)[0] * track.get(i)[1]
+ twoArr[track.get(i)[2] - 1][0] * twoArr[track.get(i)[2] - 1][1];
maxStateValue = Math.max(maxStateValue, stateValue);
used[track.get(i)[2] - 1] = true;
}
} else {
//不是附件直接判断钱是否<=canUsedMoney
if (countMoney <= canUsedMoney) {
stateValue = stateValue + track.get(i)[0] * track.get(i)[1];
maxStateValue = Math.max(maxStateValue, stateValue);
used[track.get(i)[3]] = true;
}
}
}
for (int i = start; i < twoArr.length; i++) {
track.add(twoArr[i]);
dfs(twoArr, i + 1, track, canUsedMoney);
track.removeLast();
}
}
} 
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
