【代码+详解】算法题 : 骨头收集者

❗❗❗必看:

下列题我全部都使用 Java 语言写的,并且均可以提交成功,获得Accepted 结果的. 如果代码和详解看了之后,对答案有任何疑问,都可以在评论区提出来,我都会一个一个回答.

❗❗❗感谢大家的支持,如果喜欢我的博客,关注 点赞 收藏 评论一波,非常感谢!!!

文章目录

• 题目:骨头收集者
• • 测试样例
  • 代码
  • 详解
  • • 初步思路
    • 具体步骤
    • 总结方法

      题目:骨头收集者

      许多年前，在泰迪的家乡，有一个被称为“骨头收集者”的人。这个人喜欢收集各种骨头，比如狗的、牛的，甚至还去坟墓……

      骨头收集者有一个容积为V的大袋子，沿途收集骨头时有很多骨头，显然，不同的骨头有不同的价值和不同的体积，现在给定每个骨头沿途的价值，你能计算出骨头收集者能获得的最大总价值吗？

      输入

      第一行包含一个整数T，表示案例的数量。

      接下来是T个案例，每个案例有三行，第一行包含两个整数N，V，(N public static void main(String[] args){ Scanner sc = new Scanner(System.in); int k = sc.nextInt(); while(k--0) { int N = sc.nextInt();//骨头的数量 int V = sc.nextInt();//背包的容量 int[] values = new int[N];//物品的价值 int [] volumes = new int[N];//物品的重量 for(int i = 0;i values[i] = sc.nextInt();//为每个物品依次读入价值 } for(int i= 0;i volumes[i] = sc.nextInt();//为每个物品依次读入重量 } int result = maxValue(N,V,values,volumes); System.out.println(result); } } private static int maxValue(int N, int V, int[] values, int[] volumes) { //创建一个二维数组,用来表示在前i个物品在容量不超过j的时候可以获得的最大价值 int[][] dp = new int[N+1][V+1]; for(int i = 1;i for(int j = 0;j dp[i][j] = dp[i-1][j]; if(j=volumes[i-1]) { dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - volumes[i - 1]] + values[i - 1]); // 选第i个骨头 } } } return dp[N][V]; } }