题解 | #购物单#
购物单
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);
}
}
查看22道真题和解析
