2023年8月1日发(作者：)

华为上机试---购物单（算法：背包问题）题⽬描述王强今天很开⼼，公司发给N元的年终奖。王强决定把年终奖⽤于购物，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是⼀些主件与附件的例⼦：主件电脑书柜书桌⼯作椅附件打印机，扫描仪图书台灯，⽂具⽆如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有 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 ）。输⼊例⼦:1000 5800 2 0400 5 1300 5 1400 3 0500 2 0输出例⼦:2200

找到了⼀个很棒的java程序，但是我没看懂那个result[][]的⽤法。。。

import r;/** * 思路：给定购物单，逐级增加⾦额和件数，直到达到购物单上限⽌（商品件数或者总⾦额）； * 逐级计算出所对应的最⼤乘积值，并在此过程中，⽐较出到此级为⽌的乘积最⼤值

* Author: 王俊超 Time: 2016-01-24 08:30

* CSDN:/derrantcm Github: /Wang-Jun-Chao * Declaration: All Rights Reserved

*/public class Main { public static void main(String[] aStrings) { Scanner scanner = new Scanner(); // Scanner scanner = new // Scanner(ssLoader().getResourceAsStream("")); while (t()) { // 总的钱数 int total = t(); // 希望购买物品的个数 int num = t(); // 每个物品的价格 int[] price = new int[num + 1]; // 每个物品的权重 int[] value = new int[num + 1]; // 是主件还是附件 int[] check = new int[num + 1]; for (int i = 1; i <= num; i++) { // 读取输⼊数据 price[i] = t(); value[i] = t(); check[i] = t(); } // 结果数组 // ⾏代表物品个数，列代表钱数 int[][] result = new int[num + 1][total + 1]; for (int i = 1; i <= total; i++) { for (int j = 1; j <= num; j++) { // 如果是附件 if (check[j] > 0) { // result[j-1][i-price[j]] 表⽰使⽤i-price[j]的总钱数，最多买j-1个物品的最⼤值 // 总的钱数⽐(当前物品+他的主件)所需要的钱多 if (i > price[j] + price[(check[j])]) { int w = result[j - 1][i - price[j]] + value[j] * price[j]; result[j][i] = w > result[j - 1][i] ? w : result[j - 1][i]; } } else { // 总钱数可以买主件 if (i >= price[j]) { int w = result[j - 1][i - price[j]] + value[j] * price[j]; result[j][i] = w > result[j - 1][i] ? w : result[j - 1][i]; } } } } n(result[num][total]); } (); }}

2023年8月1日发(作者：)

华为上机试---购物单（算法：背包问题）题⽬描述王强今天很开⼼，公司发给N元的年终奖。王强决定把年终奖⽤于购物，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是⼀些主件与附件的例⼦：主件电脑书柜书桌⼯作椅附件打印机，扫描仪图书台灯，⽂具⽆如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有 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 ）。输⼊例⼦:1000 5800 2 0400 5 1300 5 1400 3 0500 2 0输出例⼦:2200

找到了⼀个很棒的java程序，但是我没看懂那个result[][]的⽤法。。。

import r;/** * 思路：给定购物单，逐级增加⾦额和件数，直到达到购物单上限⽌（商品件数或者总⾦额）； * 逐级计算出所对应的最⼤乘积值，并在此过程中，⽐较出到此级为⽌的乘积最⼤值

* Author: 王俊超 Time: 2016-01-24 08:30

* CSDN:/derrantcm Github: /Wang-Jun-Chao * Declaration: All Rights Reserved

*/public class Main { public static void main(String[] aStrings) { Scanner scanner = new Scanner(); // Scanner scanner = new // Scanner(ssLoader().getResourceAsStream("")); while (t()) { // 总的钱数 int total = t(); // 希望购买物品的个数 int num = t(); // 每个物品的价格 int[] price = new int[num + 1]; // 每个物品的权重 int[] value = new int[num + 1]; // 是主件还是附件 int[] check = new int[num + 1]; for (int i = 1; i <= num; i++) { // 读取输⼊数据 price[i] = t(); value[i] = t(); check[i] = t(); } // 结果数组 // ⾏代表物品个数，列代表钱数 int[][] result = new int[num + 1][total + 1]; for (int i = 1; i <= total; i++) { for (int j = 1; j <= num; j++) { // 如果是附件 if (check[j] > 0) { // result[j-1][i-price[j]] 表⽰使⽤i-price[j]的总钱数，最多买j-1个物品的最⼤值 // 总的钱数⽐(当前物品+他的主件)所需要的钱多 if (i > price[j] + price[(check[j])]) { int w = result[j - 1][i - price[j]] + value[j] * price[j]; result[j][i] = w > result[j - 1][i] ? w : result[j - 1][i]; } } else { // 总钱数可以买主件 if (i >= price[j]) { int w = result[j - 1][i - price[j]] + value[j] * price[j]; result[j][i] = w > result[j - 1][i] ? w : result[j - 1][i]; } } } } n(result[num][total]); } (); }}