❤重点❤】【牛客网 - 华为整机测试】HJ16 购物清单 - 动态规划
最编程
2024-04-19 18:50:49
...
HJ16 购物单
题目描述
解题思路
这题其实是0-1背包问题，但是附加了条件
具体思路就是构造物品类，然后对主件判断是否有附件，若有附件则依次添加，根据主件、附件1、附件2的组合有四种情况
- 只有主件
- 主件+附件1
- 主件+附件2
- 主件+附件1+附件2
根据以上情况转化问题为经典的 01背包问题 ，接着就是套公式动态规划即可
经典背包问题回顾
问题描述：有一个背包可以装物品的总重量为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个物品要么放入背包，要么不放入背包。
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
for j in range(1,n+1):
if j-w[i]>=0:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])
else:
dp[i][j] = dp[i-1][j]
return dp[m][n]
本题解题思路
购物车本质上还是0-1背包问题，只不过多了主件和附件。
-
假设先不看附件，那么就和0-1背包一样了。附件不能单独出现，要依赖于主件。
对应于背包问题，主件的个数就是物品的个数，考虑每个主件时要考虑可能出现的情况。 输入例子: 1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0 在当前的例子当中物品的个数就是3。 -
考虑每个物品时要考虑每种可能出现的情况，1、主件，2、主件+附件1，3、主件+附件2，4、主件+附件1+附件2，不一定每种情况都出现，只有当存在附件时才会出现对应的情况。
w[i][k]表示第i个物品的第k种情况，k的取值范围0~3，分别对应以上4中情况，v[i][k]表示第i个物品对应第k种情况的价值，现在就把购物车问题转化为了0-1背包问题。 状态转移方程可以定义为 dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i][k]]+v[i][k]) dp[i-1][j]表示当前物品不放入背包，w[i][k]表示第i个主件对应第k中情况，即当前第i个物品的4中情况中价值最大的要么放入背包，要么不放入背包。 需要注意：dp[i][j] = max(物品不放入背包，主件，主件+附件1，主件+附件2，主件+附件1+附件2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
for j in range(1,n+1):
max_i = dp[i-1][j]
for k in range(len(w[i])):
if j-w[i][k]>=0:
max_i = max(max_i, dp[i-1][j-w[i][k]]+v[i][k])
dp[i][j] = max_i
print(dp[m][n])
代码
/**
* Copyright (C), 2019-2021
* author candy_chen
* date 2021/4/7 17:15
*
* @Classname HJ16
* Description: 购物单
*/
import java.util.Scanner;
/**
* 加了附加条件的背包问题
*/
public class Main {
static class Good{
int v;
int vp;
public Good(int v,int vp){
this.v = v;
this.vp = vp;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//总钱数
int N = sc.nextInt();
//购买物品个数
int m = sc.nextInt();
int[] f = new int[N + 1];
//分组，goods[i][0]为主件，goods[i][1]为附件1，goods[i][2]为附件2
Good[][] goods1 = new Good[60][4];
for (int i = 1; i <= m; i++) {
int v = sc.nextInt(); //该物品的价格
int p = sc.nextInt(); //该物品的重要度
int q = sc.nextInt(); //该物品是主件还是附件 q=0 主件； q > 0 附件，是主件所属的编号
Good t = new Good(v,v*p);
if (q == 0){
goods1[i][0] = t;
}else {
if (goods1[q][1] == null){
goods1[q][1] = t;
}else {
goods1[q][2] = t;
}
}
}
for (int i = 1; i <= m; i++) { // m （ <60 ）为希望购买物品的个数
for (int j = N; j >= 0 && goods1[i][0] != null; j--) {
//以下代码从分组中选择价值最大的。共五种情况：不选主件，选主件，选附件1和主件，选附件2和主件，选附件1和附件2和主件
// 主件
Good master = goods1[i][0];
//情形1：不买主件
int max = f[j];
// 情形2: 购买主件
if (j >= master.v && max < f[j - master.v] + master.vp) {
//f[j - master.v] ： 当用钱买下主件后剩余的钱，能买到的最大权重
max = f[j - master.v] + master.vp;
}
// 情形3：购买主件和附件1（附件1存在即代表主件存在）
int vt;
if (goods1[i][1] != null) {
if (j >= (vt = master.v + goods1[i][1].v)
&& max < f[j - vt] + master.vp + goods1[i][1].vp) {
max = f[j - vt] + master.vp + goods1[i][1].vp;
}
}
// 附件2存在即代表主件及附件1存在）
// 情形4: 购买主件及附件2
if (goods1[i][2] != null) {
if (j >= (vt = master.v + goods1[i][1].v + goods1[i][2].v)
&& max < f[j - vt] + master.vp + goods1[i][1].vp + goods1[i][2].vp) {
max = f[j - vt] + master.vp + goods1[i][1].vp + goods1[i][2].vp;
}
}
f[j] = max;
}
}
System.out.println(f[N]);
}
}