当前位置：首页 > news >正文

HJ16 购物单

news 来源：原创 2025/9/6 3:53:42

https://www.nowcoder.com/exam/oj/ta?tpId=37

HJ16 购物单

描述
王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件。
主件可以没有附件，至多有 2个附件。附件不再有从属于自己的附件。如果要买归类为附件的物品，必须先买该附件所属的主件，且每件物品只能购买一次。
王强查到了每件物品的价格，而他只有 n 元的预算。为了先购买重要的物品，他给每件物品规定了一个重要度，用整数1∼5 表示。
他希望在花费不超过 n 元的前提下，使自己的满意度达到最大。

方法一:动态规划


import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 预算int n = in.nextInt();// 物品总数int m = in.nextInt();Good[] goods = new Good[m];for (int i = 0; i < m; i++) {goods[i] = new Good();}// 组装m件商品的信息for (int i = 0; i < m; i++) {int v = in.nextInt();int w = in.nextInt();int parentId = in.nextInt();goods[i].id = i;goods[i].v = v;goods[i].vw = v * w;goods[i].parentId = parentId;if (parentId == 0) {goods[i].isMain = true;} else if (goods[parentId - 1].a1 == -1) {goods[parentId - 1].a1 = i;} else if (goods[parentId - 1].a2 == -1) {goods[parentId - 1].a2 = i;}}int pd[][] = new int[m + 1][n + 1];/**对金额n 和商品数量m进行动态规划*  从pd[0][0]依次推算 pd[0][n]，*  pd[1][0]依次推算 pd[1][n]**  pd[i][0]依次推算 pd[i][n]**  pd[m][0]依次推算 pd[m][n]**  所以双层循环的外层是  m* pd[0][j] 为第一行 必等于0 ；* pd[i][0] 为第一列，必等于0* int数组的默认值刚好是0，所以不用初始化* 且直接从i= 1 、j=1开始循环* */for (int i = 1; i <= m; i++) {for (int j = 10; j <= n; j += 10) { //因为商品价格必定为10的倍数，所以j从10开始，每次加10// 1、 pd[i][j] 初始化为 pd[i-1][j];pd[i][j] = pd[i - 1][j];/**** 2、判断第i行的商品是否为主商品*  由于pd的行是 [0,m]左闭右闭区间共m+1行，商品数组goods是[0,m)0到m左闭右开区间*  所以外层循环的第 i 行对应的商品是 good[i-1]*/if (!goods[i - 1].isMain) {// 非主商品不能单独购买，所以pd[i][j] = pd[i-1][j]，（如果主商品在前面也没关系，因为判断主商品的pd逻辑，会考虑附属商品的价值）continue;}// 3、主商品的价值计算有多种情况，多种情况取最大值// 3.1 不考虑附属商品时  pd[i][j] 和 (pd[i-1][j-当前商品价格]+当前商品价值) 取最大值,(第一步里面 pd[i][j]已经初始化为 pd[i-1][j] 了)if (j >= goods[i - 1].v) {// 需要判断当前总金额是否大于当前商品价格，，否则不能单独购买(强买会数组越界异常)pd[i][j] = Math.max(pd[i][j], pd[i - 1][j - goods[i - 1].v] + goods[i - 1].vw);}/***  3.2 当前商品有附属商品A1，附属a1就是good[goods[i-1].a1] ,*  pd[i][j] 和 pd[i][j-当前商品价格-A1的价格]+当前商品价值+A1商品的价值 取最大值*/if (goods[i - 1].a1 != -1 && j >= goods[i - 1].v + goods[goods[i - 1].a1].v) {pd[i][j] = Math.max(pd[i][j], pd[i - 1][j - goods[i - 1].v - goods[goods[i - 1].a1].v] + goods[i - 1].vw + goods[goods[i - 1].a1].vw);}/***  3.2 当前商品有附属商品A2，附属a2就是good[goods[i-1].a2]*  pd[i][j] 和 pd[i][j-当前商品价格-A2的价格]+当前商品价值+A2商品的价值 取最大值*/if (goods[i - 1].a2 != -1 && j >= goods[i - 1].v + goods[goods[i - 1].a2].v) {pd[i][j] = Math.max(pd[i][j], pd[i - 1][j - goods[i - 1].v - goods[goods[i - 1].a2].v] + goods[i - 1].vw + goods[goods[i - 1].a2].vw);}/*** 3.3 最后比较两种附件都买时的最大值，依然要先比较价格* */if (goods[i - 1].a1 != -1 && goods[i - 1].a2 != -1 && j >= goods[i - 1].v + goods[goods[i - 1].a1].v + goods[goods[i - 1].a2].v) {pd[i][j] = Math.max(pd[i][j], pd[i - 1][j - goods[i - 1].v - goods[goods[i - 1].a1].v - goods[goods[i - 1].a2].v] + goods[i - 1].vw + goods[goods[i - 1].a1].vw + goods[goods[i - 1].a2].vw);}}}// 循环结束，得到pd[][]二维数组的所有值，输出p[n][m]System.out.println(pd[m][n]);}}class Good {// 商品idint id;// 价格int v;// 满意度 = 价格*重要度int vw;// 父商品idint parentId;// 是否组商品boolean isMain;// 没有附件时，a1a2 必须是负数 ，必定不能是0 因为 第一个商品的编号真的是0// 第一个附属商品的编号int a1 = -1;// 第二个附属商品的编号int a2 = -1;
}

方法二：动态规划（空间压缩）

具体方法
基本与思路一一样，但是在本题中，由于我们是否取第i个商品时的数组只与是否取第i-1个商品时的数组相关，所以可以进行空间压缩，将时间复杂度压缩到O(N)，但需注意逆循环，防止前面修改被后面应用。

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[] goods = new Goods[m];for(int i = 0; i < m; i++){goods[i] = new Goods();}for(int i = 0; i < m; i++){int v = sc.nextInt();int p = sc.nextInt();int q = sc.nextInt();goods[i].v = v;goods[i].p = p * v;  // 直接用p*v，方便后面计算if(q==0){goods[i].main = true;}else if(goods[q-1].a1 == -1){goods[q-1].a1 = i;}else{goods[q-1].a2 = i;}}int[] dp = new int[N+1];for(int i = 1; i <= m; i++){for(int j = N; j >= 0; j--){if(!goods[i-1].main){continue;}if(j>=goods[i-1].v){dp[j] = Math.max(dp[j], dp[j-goods[i-1].v] + goods[i-1].p);}if(goods[i-1].a1 != -1 && j >= goods[i-1].v + goods[goods[i-1].a1].v){dp[j] = Math.max(dp[j], dp[j-goods[i-1].v - goods[goods[i-1].a1].v] + goods[i-1].p + goods[goods[i-1].a1].p);}if(goods[i-1].a2 != -1 && j >= goods[i-1].v + goods[goods[i-1].a2].v){dp[j] = Math.max(dp[j], dp[j-goods[i-1].v - goods[goods[i-1].a2].v] + goods[i-1].p + goods[goods[i-1].a2].p);}if(goods[i-1].a1 != -1 && goods[i-1].a2 != -1 &&  j >= goods[i-1].v + goods[goods[i-1].a1].v + goods[goods[i-1].a2].v){dp[j] = Math.max(dp[j], dp[j-goods[i-1].v - goods[goods[i-1].a1].v - goods[goods[i-1].a2].v] + goods[i-1].p + goods[goods[i-1].a1].p + goods[goods[i-1].a2].p);}}}System.out.println(dp[N]);}
}class Goods {int v;int p;boolean main = false;int a1 = -1;  //定义附件1的编号int a2 = -1;  //定义附件2的编号
}

HJ16 购物单

方法一:动态规划

方法二：动态规划（空间压缩）

相关文章：