【每天一道算法题】华为机试HJ16：购物单（解析加源码）

本专栏将会从基础开始，循序渐进，每天刷一道算法题，也请大家多多支持。数据结构虽然难，但只要肯坚持，一定能学好，希望大家都能够从中获益。
专栏地址: 每天一道算法题专栏 数据结构专栏
本专栏的所有代码都将更新在Gitee上，项目地址：项目地址

准备好了吗
Let’s go!

文章目录

• • 👀问题描述
  • 💬相关知识点介绍
  • ✏️ 思路解析
  • ✨代码实现

👀问题描述

王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：

主件	附件
电脑	打印机，扫描仪
书柜	图书
书桌	台灯，文具
工作椅	无

如果要买归类为附件的物品，必须先买该附件所属的主件，且每件物品只能购买一次。
每个主件可以有$0$个、$1$ 个或 $2$ 个附件。附件不再有从属于自己的附件。
王强查到了每件物品的价格（都是 $10$ 元的整数倍），而他只有 $N$ 元的预算。除此之外，他给每件物品规定了一个重要度，用整数 $1$ ~ $5$ 表示。他希望在花费不超过 $N$ 元的前提下，使自己的满意度达到最大。

满意度是指所购买的每件物品的价格与重要度的乘积的总和，假设设第$i$件物品的价格为$v[i]$，重要度为$w[i]$，共选中了$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$，现有$N$个物品，每个物品中$w[i]$，价值$v[i]$，用背包装物品，能装的最大价值是多少？

定义状态转移数组$dp[i][j]$，表示前i个物品，背包重量为j的情况下能装的最大价值。

例如，$dp[3][4]=6$，表示用前$3$个物品装入重量为4的背包所能获得的最大价值为$6$，此时并不是$3$个物品全部装入，而是$3$个物品满足装入背包的条件下的最大价值。

状态转移方程：

$dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])$

$dp[i-1][j]$表示当前物品不放入背包，$dp[i-1][j-w[i]]+v[i]$表示当前物品放入背包，即当前第$i$个物品要么放入背包，要么不放入背包。

✏️ 思路解析

本题设主件个数为$n$，奖金数量为$M$，每个主件对应的价格为$v$，每个主件对应的重要程度为$w$。$d[i][j]$表示从前i个主件中选取，奖金数量为j的情况下，所获得的最大价格*重要程度累加和。另外注意到一个小细节：每个主件只能有$0～2$个附件，最多才$4$种搭配方式$(00,01,10,11)$，得到如下状态公式：

1. 如果$j>=v[i-1]$，那么$dp[i][j]=max(dp[i][j-v[i-1]]+v[i-1]\ast w[i-1],dp[i-1][j],$➜➜➜➜)（➜➜➜➜表示有附件的情况，为了简化问题，我们把它放到下面讲）
2. 如果$j<v[i-1]$，那么$dp[i][j]=dp[i-1][j]$
3. 基准1: $dp[0][..]=0$
4. 基准2: $dp[..][0]=0$

对于状态公式的解释：

1. 如果总奖金数能涵盖当前物品，那么选取包含当前物品和不包含当前物品两种情况下最大的累加和
2. 如果总奖金数不能涵盖当前物品，那么直接取前$i-1$个物品的最大累加和
3. 基准1: 商品个数为0，再怎么加也是0
4. 基准2: 总奖金数为0，同样再怎么加也是0

其实上面的这些，除了➜➜➜➜之外的其他部分，和0/1背包问题完全一致，接下来我们分析➜➜➜➜:

1. 如果没有附件，则跳过
2. 如果附件数为1，且总奖金容得下附件，那么取最大值
3. 如果附件数为2…

✨代码实现

//已AC
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;public class HJ0006 {static class Product{public int price;       //价钱public int importance;  //重要度public int sub;         //表示该物品是主件还是附件。如果等于0 ，表示该物品为主件，如果大于0 ，表示该物品为附件， 值表示所属主件的编号public int satisfy;     //满意度public List<Product> subList = new LinkedList<Product>(); //如果是主件，则存放对应的子件public Product(int price, int importance, int sub) {this.price = price;this.importance = importance;this.sub = sub;}}public static void main(String[] args) {Scanner sc = new Scanner(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 = new ArrayList<>();//第0个不用，从第1个开始计数productList.add(new Product(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]);Product Product1 = new Product(price,importance,sub);Product1.satisfy = price * importance;productList.add(Product1);}//将附件添加到相应的主件对象中for(int i=1;i<=totalObject;i++){Product Product1 = productList.get(i);if(Product1.sub != 0){productList.get(Product1.sub).subList.add(Product1);}}int[][] dp = new int[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);}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！