【Java】华为机试题——购物单

àì夳堔傛蜴生んèń 2022-01-07 08:17 317阅读 0赞

**题目描述**  
王强今天很开心，公司发给N元的年终奖。王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：  
![在这里插入图片描述][20190625161810830.png]  
如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有 0 个、 1 个或 2 个附件。附件不再有从属于自己的附件。王强想买的东西很多，为了不超出预算，他把每件物品规定了一个重要度，分为 5 等：用整数 1 ~ 5 表示，第 5 等最重要。他还从因特网上查到了每件物品的价格（都是 10 元的整数倍）。他希望在不超过 N 元（可以等于 N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。  
设第 j 件物品的价格为 v\[j\] ，重要度为 w\[j\] ，共选中了 k 件物品，编号依次为 j 1 ， j 2 ，……， j k ，则所求的总和为：  
v\[j 1 \]\*w\[j 1 \]+v\[j 2 \]\*w\[j 2 \]+ … +v\[j k \]\*w\[j k \] 。（其中 \* 为乘号）  
请你帮助王强设计一个满足要求的购物单。  
**输入描述**

输入的第 1 行，为两个正整数，用一个空格隔开：N m
    
    （其中 N （ <32000 ）表示总钱数， m （ <60 ）为希望购买物品的个数。）
    
    
    从第 2 行到第 m+1 行，第 j 行给出了编号为 j-1 的物品的基本数据，每行有 3 个非负整数 v p q
    
    
    （其中 v 表示该物品的价格（ v<10000 ）， p 表示该物品的重要度（ 1 ~ 5 ）， q 表示该物品是主件还是附件。如果 q=0 ，表示该物品为主件，如果 q>0 ，表示该物品为附件， q 是所属主件的编号）

**输出描述**

输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（ <200000 ）。

package 牛客;
    
    import java.util.Scanner;
    
    public class 购物单 {
        
        public static int getmax(int[] j, int[] p, int[] q, int m, int n) {
        
            int[][] a = new int[m + 1][n + 1];
            for (int i = 1; i <= m; i++) {
        
                for (int l = 1; l <= n; l++) {
        
                    if (q[i-1] == 0) {
        
                        if (p[i-1] <= l) {
        
                            a[i][l] = Math.max(a[i - 1][l], a[i - 1][l - p[i - 1]] + j[i-1]);
                        }
                    }
                        if(p[i-1]>0){
        
                        if (p[i-1] + p[q[i-1]] <= l) {
        
                            a[i][l] = Math.max(a[i - 1][l], a[i - 1][l - p[i - 1]] + j[i-1]);
                        }
                    }
                }
            }
            return a[m][n];
        }
        public static void main(String[] args) {
        
            Scanner s=new Scanner(System.in);
            while(s.hasNext()){
        
                int N=s.nextInt();//总钱数N
                int m=s.nextInt();//商品个数
                int []p=new int[m];//商品价格
                int []v=new int[m];//重要度
                int []q=new int[m];//主or附
                int []j=new int[m];//v*p
                for(int i=0;i<m;i++){
        
                    p[i]=s.nextInt();
                    v[i]=s.nextInt();
                    q[i]=s.nextInt();
                    j[i]=v[i]*p[i];
                }
                System.out.println(getmax(j,p,q,m,N));
            }
        }
    
    }

![在这里插入图片描述][2019062517242913.png]

[20190625161810830.png]: /images/20211227/04a70314591e4216a74a867cc8ca2a0b.png
[2019062517242913.png]: /images/20211227/83f8d551fed74f7e910184699656521f.png