题解 | #购物单#
购物单
https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
我是用动态规划的常用解题思路来解的:
for 状态1 in 状态1的所有取值: for 状态2 in 状态2的所有取值: for ... dp[状态1][状态2][...] = 择优(选择1,选择2...)不过在这之前先找到了数组的最大公因数,让各数据除以公因数,最后计算的结果乘以公因数就可以了,下面是具体代码:
import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int totalMoney = sc.nextInt(); int totalNum = sc.nextInt(); int[] moneys = new int[totalNum]; int[] importants = new int[totalNum]; int[] parents = new int[totalNum]; for(int i=0;i<totalNum;i++){ moneys[i] = sc.nextInt(); importants[i] = sc.nextInt(); parents[i] = sc.nextInt(); } //求出最大公因数 int gys = maxGys(moneys); totalMoney = totalMoney / gys; for(int i=0;i<moneys.length;i++){ moneys[i] = moneys[i] / gys; } Node[][] dp = new Node[totalNum+1][totalMoney+1]; for(int i = 0;i<=totalNum;i++){ for(int m = 0;m <= totalMoney;m++){ if(i == 0 || m == 0){ dp[i][m] = new Node(); continue; } dp[i][m] = new Node(); if(m - moneys[i-1] < 0){ dp[i][m] = dp[i-1][m]; }else{ if(parents[i-1] == 0){//父节点 int lastV = dp[i-1][m].value; int andV = dp[i-1][m-moneys[i-1]].value + (moneys[i-1] * importants[i-1]); if(lastV > andV){ dp[i][m] = dp[i-1][m]; }else{ dp[i][m].value = andV; //把父节点记录进去 dp[i][m].parents.add(i); dp[i][m].parents.addAll(dp[i-1][m-moneys[i-1]].parents); } }else{//子节点 if(dp[i-1][m-moneys[i-1]].parents.contains(parents[i-1])){//里面有该子节点的父节点 int lastV = dp[i-1][m].value; int andV = dp[i-1][m-moneys[i-1]].value + (moneys[i-1] * importants[i-1]); if(lastV > andV){ dp[i][m] = dp[i-1][m]; }else{ dp[i][m].value = andV; //把父节点记录进去 dp[i][m].parents.addAll(dp[i-1][m-moneys[i-1]].parents); } }else{//无,则继续判断 if(m - moneys[i-1] - moneys[parents[i-1]-1] < 0){//不够添加父节点 dp[i][m] = dp[i-1][m]; }else{//够添加 int lastV = dp[i-1][m].value; if(dp[i-1][m-moneys[i-1]-moneys[parents[i-1]-1]].parents.contains(parents[i-1])){//已经含有该父节点了 int andV = dp[i-1][m-moneys[i-1]-moneys[parents[i-1]-1]].value + (moneys[i-1] * importants[i-1]); if(lastV > andV){ dp[i][m] = dp[i-1][m]; }else{ dp[i][m].value = andV; //把父节点记录进去 dp[i][m].parents.addAll(dp[i-1][m-moneys[i-1]-moneys[parents[i-1]-1]].parents); } }else{ int andV = dp[i-1][m-moneys[i-1]-moneys[parents[i-1]-1]].value + (moneys[i-1] * importants[i-1]) + moneys[parents[i-1]-1] * importants[parents[i-1]-1]; if(lastV > andV){ dp[i][m] = dp[i-1][m]; }else{ dp[i][m].value = andV; //把父节点记录进去 dp[i][m].parents.add(parents[i-1]); dp[i][m].parents.addAll(dp[i-1][m-moneys[i-1]-moneys[parents[i-1]-1]].parents); } } } } } } } } System.out.println(dp[totalNum][totalMoney].value * gys); } /** * 满意度 类 */ static class Node{ //满意度 public int value; //含有的父节点 public List<Integer> parents = new ArrayList<>(); } /** * 最大公因数 */ private static int maxGys(int[] moneys){ List<Integer> number = new ArrayList<>(); for(int i : moneys){ number.add(i); } while(number.size()>1) {//如果仅剩一个数,那就是最后计算出的最大公因数 int temp = gcd(number.get(0), number.get(1));//循环取出开头的两个数,计算他俩的最大公因数 /*将他俩移除(为啥都是0,刚开始我也是0,1,但是移除完第一个后,后面的数会再次向前移一位, 也就是说你要移除的第二个数就是现在位置为0的数)*/ number.remove(0); number.remove(0); //将新计算的最大公因数进行添加进ArrayList的开头 number.add(0,temp); } return number.get(0);//返回这组数的最大公因数 } //迭代计算两个最大公因数的方法 private static int gcd(int m,int n){ if(n == 0){ return m; } int r = m%n; return gcd(n,r); } }