网站自己推广,嘉兴网站制作哪家专业,广州有什么好玩的景点,淘宝做链接有哪些网站可以做许多年前#xff0c;在泰迪的家乡#xff0c;有一个人叫“骨头收集者”。这个人喜欢收集各种骨头#xff0c;比如狗的、牛的#xff0c;他也去坟墓...... 骨头采集者有一个体积为V的大袋子#xff0c;在他收集的旅途中有很多骨头#xff0c;显然#xff0c;不同的… 许多年前在泰迪的家乡有一个人叫“骨头收集者”。这个人喜欢收集各种骨头比如狗的、牛的他也去坟墓...... 骨头采集者有一个体积为V的大袋子在他收集的旅途中有很多骨头显然不同的骨头有不同的价值和不同的体积现在给定每块骨头沿途的价值你能计算出骨头收集者可以得到的总价值的最大值吗 输入 第一行包含一个整数 T 即案例数。 后面是T个案例每个案例三行第一行包含两个整数NVN 1000V 1000代表骨头的数量和他的袋子的体积。第二行包含 N 个整数表示每个骨骼的值。第三行包含 N 个整数表示每块骨头的体积。 输出 每行一个整数表示总值的最大值此数字将小2^31。 import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);int T sc.nextInt();//案例数量while (T-- ! 0) {int n sc.nextInt();//骨头个数int v sc.nextInt();//背包体积int[] money new int[n 1];//注意定义数组要1里面要包括为0时的情况int[] volume new int[n 1];for (int i 1; i n; i) {//每个骨头的价格money[i] sc.nextInt();}for (int i 1; i n; i) {//每个骨头的体积volume[i] sc.nextInt();}int[] dp new int[v 1];//定义多个体积不同的背包存储当前体积的最大价值for (int i 1; i n; i) {//先循环每件物品for (int j v; j volume[i]; j--) {//再循环背包容量从大到小依次循环直至背包放不进去当前商品dp[j] Integer.max(dp[j], money[i] dp[j - volume[i]]);//依次存储在只考虑i件物品下的最大价值比较不放入第i件物品和放入第i件物品的价值}}System.out.println(dp[v]);//打印背包体积为v时的最大价值}}
}
