题解 | #购物单#
购物单
https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
import java.util.Scanner; import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); // // 注意 hasNext 和 hasNextLine 的区别 // while (in.hasNextInt()) { // 注意 while 处理多个 case // int a = in.nextInt(); // int b = in.nextInt(); // System.out.println(a + b); // } //1. 首先定义一个物品类 Good //2. 入参赋值 int money = in.nextInt(); //总钱数 int num = in.nextInt(); //物品总件数 //3. 入参校验 if(money<=0 || num<=0){ System.out.println(0); } //4. 填充物品数组 + 生成一个id对应的满意度数组,方便后序使用 + 记录物品最小的价格,后序可做剪枝 + 记录第一个主件的id Good[] goods = new Good[num+1]; int[] sat = new int[num+1]; int minVal = Integer.MAX_VALUE; // 后面要取最小这里要赋值个最大值 int firstMainId = 0; //4.1 物品数组从1开始,因为附件的所属主件id也是从1开始 for(int i=1; i<= num; i++){ int v = in.nextInt(); int p = in.nextInt(); int q = in.nextInt(); Good g = new Good(v,p,q); goods[i] = g; sat[i] = v*p; //满意度=每件物品的价格*重要度乘积 minVal = Math.min(minVal, v); } //4.2 如果q大于0,则需要为对应的主件打上附件标签。(分两个for执行因为有可能附件先来,此时主键还未创建) for(int i=1; i<=num; i++){ int q = goods[i].q; if(q >0){ if(goods[q].a1 ==-1){ goods[q].setA1(i); }else { goods[q].setA2(i); } }else if(q==0 && firstMainId==0){ //记录第一个主件 firstMainId =i; } } //5. 解题思路: 动态规划dp[i][j] //5.1 i,j的代表意义,i个物品(注意是总i个,不是取了i个),j金钱可达到的最大满意度为dp[i][j] //5.2 递推公式: /** 共有5种情况 1) 不购买当前物品: dp[i][j] = dp[i-1][j] 2) 购买当前物品,但不够买当前物品的附件: dp[i][j] = dp[i-1][j-goods[i].v] + sat[i]; 3) 购买当前物品,且购买附件1(如有);dp[i][j] = dp[i-1][j-(goods[i].v)-(goods[goods[i].a1].v)] + sat[i] + sat[goods[i].a1] 4)购买当前物品,且购买附件2(如有);dp[i][j] = dp[i-1][j-(goods[i].v)-(goods[goods[i].a2].v)] + sat[i] + sat[goods[i].a2] 5)购买当前物品,且购买附件1,2(如有),dp[i][j] = dp[i-1][j-(goods[i].v)-(goods[goods[i].a1].v)-(goods[goods[i].a2])] + sat[i] + sat[goods[i].a1] + sat[goods[i].a2] 以上五种情况,第1)可以搭配后面四种情况,后面四种情况是根据物品情况才有, 所以dp[i][j]= max(1)情况,2)情况(如有),3)情况(如有),4情况(如有),5情况(如有)) */ int[][] dp = new int[num+1][money+1]; //注意此处i要从1开始,因为跟物品的id对应上, j可以从0开始 for(int i =1; i<=num ; i++){ for(int j=0; j<=money; j++){ //6.1 【初始化dp数组】,j=0 无钱 dp[i][0]=0; if(j==0){ dp[i][j] =0; continue; } //6.2 【初始化dp数组】,当i<第一个主件id,dp[i][j]=0; 因为附件不可以单独购买 if(i<firstMainId){ dp[i][j] =0; continue; } //7.1 【剪枝】:如果j< 最便宜的价格,则也直接等于0 if(j < minVal){ dp[i][j] =0; continue; } //其他的均初始化dp[i][j]为情况1) dp[i][j] = dp[i-1][j]; //7.2 【剪枝】:如果当前物品只是附件,直接等于不取附件的dp[i-1][j] continue if(goods[i].q >0){ //System.out.printf("i=%d, j=%d, dp[i][j]=%d%n", i, j, dp[i][j]); continue; } if(j>=goods[i].v){ //情况2) dp[i][j] = Math.max(dp[i][j], dp[i-1][j-goods[i].v] + sat[i]); } //条件不是互斥的,要继续用if,不是else-if //情况 3) int a1Id = goods[i].a1; if(a1Id !=-1 && j>= goods[i].v + goods[a1Id].v){ dp[i][j] = Math.max(dp[i][j], dp[i-1][j-goods[i].v-goods[a1Id].v] + sat[i] + sat[a1Id]); } int a2Id = goods[i].a2; if(a2Id !=-1 && j>= goods[i].v + goods[a2Id].v){ dp[i][j] = Math.max(dp[i][j], dp[i-1][j-goods[i].v-goods[a2Id].v] +sat[i] +sat[a2Id]); } if(a1Id !=-1 && a2Id !=-1 && j>=goods[i].v + goods[a1Id].v + goods[a2Id].v){ dp[i][j] = Math.max(dp[i][j], dp[i-1][j-goods[i].v-goods[a1Id].v-goods[a2Id].v] + sat[i] + sat[a1Id] + sat[a2Id]); } } } System.out.println(dp[num][money]); } public static class Good{ public int v; //物品价格 public int p; //物品重要度 public int q; //0主件 >0为主键id public int a1 =-1; //附件1 id(需要给个初始值,后序赋值才能判断附件1是否有值了) public int a2 =-1; //附件2 id 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; } } }