本专栏将会从基础开始，循序渐进，每天刷一道算法题，也请大家多多支持。数据结构虽然难，但只要肯坚持，一定能学好，希望大家都能够从中获益。
专栏地址: 每天一道算法题专栏 数据结构专栏
本专栏的所有代码都将更新在Gitee上，项目地址：项目地址
准备好了吗
Let’s go!
文章目录
题目来源:
牛客网
👀问题描述
王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：
主件附件电脑打印机，扫描仪书柜图书书桌台灯，文具工作椅无
如果要买归类为附件的物品，必须先买该附件所属的主件，且每件物品只能购买一次。
每个主件可以有0 0 0个、 1 1 1 个或 2 2 2 个附件。附件不再有从属于自己的附件。王强查到了每件物品的价格（都是
10 10 10 元的整数倍），而他只有 N N N 元的预算。除此之外，他给每件物品规定了一个重要度，用整数 1 1 1**~** 5 5 5 表示。他希望在花费不超过 N N N 元的前提下，使自己的满意度达到最大。满意度是指所购买的每件物品的价格与重要度的乘积的总和，假设设第
i i i件物品的价格为 v [ i ] v[i] v[i]，重要度为 w [ i ] w[i] w[i]，共选中了 k k k件物品，编号依次为 j 1 , j 2 , . . . , j k j_1,j_2,...,j_k j1,j2,...,jk，则满意度为： v [ j 1 ] ∗ w [ j 1 ] + v [ j 2 ] ∗ w [ j 2 ] + … + v [ j k ] ∗ w [ j k ] v[j_1]*w[j_1]+v[j_2]*w[j_2]+ … +v[j_k]*w[j_k] 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 是所属主件的编号）
输出描述：
输出一个正整数，为张强可以获得的最大的满意度。
💬相关知识点介绍
其实这题就是0-1背包问题
首先来看一下经典背包问题，稍作修改就可以得出这题的解答0-1背包问题
问题描述：有一个背包可以装物品的总重量为
W W W，现有 N N N个物品，每个物品中 w [ i ] w[i] w[i]，价值 v [ i ] v[i] v[i]，用背包装物品，能装的最大价值是多少？定义状态转移数组
d p [ i ] [ j ] dp[i][j] dp[i][j]，表示前i个物品，背包重量为j的情况下能装的最大价值。例如，
d p [ 3 ] [ 4 ] = 6 dp[3][4]=6 dp[3][4]=6，表示用前 3 3 3个物品装入重量为4的背包所能获得的最大价值为 6 6 6，此时并不是 3 3 3个物品全部装入，而是 3 3 3个物品满足装入背包的条件下的最大价值。状态转移方程：
d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − w [ i ] ] + v [ i ] ) dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]) dp[i][j]=max(dp[i−1][j],dp[i−1][j−w[i]]+v[i]) d p [ i − 1 ] [ j ] dp[i-1][j] dp[i−1][j]表示当前物品不放入背包， d p [ i − 1 ] [ j − w [ i ] ] + v [ i ] dp[i-1][j-w[i]]+v[i] dp[i−1][j−w[i]]+v[i]表示当前物品放入背包，即当前第 i i i个物品要么放入背包，要么不放入背包。
✏️ 思路解析
本题设主件个数为
n n n，奖金数量为 M M M，每个主件对应的价格为 v v v，每个主件对应的重要程度为 w w w。 d [ i ] [ j ] d[i][j] d[i][j]表示从前i个主件中选取，奖金数量为j的情况下，所获得的最大价格*重要程度累加和。另外注意到一个小细节：每个主件只能有 0 ～ 2 0～2 0～2个附件，最多才 4 4 4种搭配方式 ( 00 , 01 , 10 , 11 ) (00,01,10,11) (00,01,10,11)，得到如下状态公式：
- 如果 j > = v [ i − 1 ] j>=v[i-1] j>=v[i−1]，那么 d p [ i ] [ j ] = m a x ( d p [ i ] [ j − v [ i − 1 ] ] + v [ i − 1 ] ∗ w [ i − 1 ] , d p [ i − 1 ] [ j ] , dp[i][j] = max(dp[i][j-v[i-1]]+v[i-1]*w[i-1], dp[i-1][j], dp[i][j]=max(dp[i][j−v[i−1]]+v[i−1]∗w[i−1],dp[i−1][j],➜➜➜➜)（➜➜➜➜表示有附件的情况，为了简化问题，我们把它放到下面讲）
- 如果 j < v [ i − 1 ] j<v[i-1] j<v[i−1]，那么 d p [ i ] [ j ] = d p [ i − 1 ] [ j ] dp[i][j] = dp[i-1][j] dp[i][j]=dp[i−1][j]
- 基准1: d p [ 0 ] [ . . ] = 0 dp[0][..]=0 dp[0][..]=0
- 基准2: d p [ . . ] [ 0 ] = 0 dp[..][0]=0 dp[..][0]=0
对于状态公式的解释：
- 如果总奖金数能涵盖当前物品，那么选取包含当前物品和不包含当前物品两种情况下最大的累加和
- 如果总奖金数不能涵盖当前物品，那么直接取前 i − 1 i-1 i−1个物品的最大累加和
- 基准1: 商品个数为0，再怎么加也是0
- 基准2: 总奖金数为0，同样再怎么加也是0
其实上面的这些，除了➜➜➜➜之外的其他部分，和0/1背包问题完全一致，接下来我们分析➜➜➜➜:
- 如果没有附件，则跳过
- 如果附件数为1，且总奖金容得下附件，那么取最大值
- 如果附件数为2…
✨代码实现
//已ACimportjava.util.ArrayList;importjava.util.LinkedList;importjava.util.List;importjava.util.Scanner;publicclass HJ0006 {staticclassProduct{publicint price;//价钱publicint importance;//重要度publicint sub;//表示该物品是主件还是附件。如果等于0 ，表示该物品为主件，如果大于0 ，表示该物品为附件， 值表示所属主件的编号publicint satisfy;//满意度publicList<Product> subList =newLinkedList<Product>();//如果是主件，则存放对应的子件publicProduct(int price,int importance,int sub){this.price = price;this.importance = importance;this.sub = sub;}}publicstaticvoidmain(String[] args){Scanner sc =newScanner(System.in);String s = sc.nextLine();//获取总钱数与可购买的物品个数String[] s1 = s.split(" ");int totalMoney =Integer.parseInt(s1[0])/10;int totalObject =Integer.parseInt(s1[1]);//存放产品的ListArrayList<Product> productList =newArrayList<>();//第0个不用，从第1个开始计数
productList.add(newProduct(0,0,0));//获取输入的商品，并计算相应的满意度for(int i=0;i<totalObject;i++){
s = sc.nextLine();
s1 = s.split(" ");int price =Integer.parseInt(s1[0])/10;int importance =Integer.parseInt(s1[1]);int sub =Integer.parseInt(s1[2]);ProductProduct1=newProduct(price,importance,sub);Product1.satisfy = price * importance;
productList.add(Product1);}//将附件添加到相应的主件对象中for(int i=1;i<=totalObject;i++){ProductProduct1= productList.get(i);if(Product1.sub !=0){
productList.get(Product1.sub).subList.add(Product1);}}int[][] dp =newint[totalObject+1][totalMoney+1];for(int i=1;i<=totalObject;i++){for(int j=1;j<=totalMoney;j++){//获取当前的商品Product current = productList.get(i);//current.sub == 0表明是一个主件if(current.sub ==0){
dp[i][j]= dp[i-1][j];//只买主件if(j - current.price >=0){//因为dp[i][j]可能会发生变化，所以这里直接比较的是dp[i][j]
dp[i][j]=Math.max(dp[i][j],dp[i-1][j-current.price]+ current.satisfy);}//主件加附件1if(current.subList.size()>=1){//附件1Product sub1 = current.subList.get(0);if(j-current.price- sub1.price >=0){
dp[i][j]=Math.max(dp[i][j],dp[i-1][j-current.price- sub1.price]+ current.satisfy + sub1.satisfy);}}//主件加附件2if(current.subList.size()>1){//附件2Product sub2 = current.subList.get(1);if(j-current.price- sub2.price >=0){
dp[i][j]=Math.max(dp[i][j],dp[i-1][j-current.price- sub2.price]+ current.satisfy + sub2.satisfy);}}//主件加附件1和附件2if(current.subList.size()>1){Product sub1 = current.subList.get(0);Product sub2 = current.subList.get(1);if(j-current.price- sub1.price - sub2.price >=0){
dp[i][j]=Math.max(dp[i][j],dp[i-1][j-current.price- sub1.price - sub2.price]+ current.satisfy + sub1.satisfy + sub2.satisfy);}}}else{
dp[i][j]= dp[i-1][j];}}}System.out.println(dp[totalObject][totalMoney]*10);}}
本文转载自: https://blog.csdn.net/Learning_xzj/article/details/125352305
版权归原作者 不知名架构师 所有， 如有侵权，请联系我们删除。
版权归原作者 不知名架构师 所有， 如有侵权，请联系我们删除。