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

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

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

文章目录

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

题目:骨头收集者

许多年前，在泰迪的家乡，有一个被称为“骨头收集者”的人。这个人喜欢收集各种骨头，比如狗的、牛的，甚至还去坟墓……
骨头收集者有一个容积为V的大袋子，沿途收集骨头时有很多骨头，显然，不同的骨头有不同的价值和不同的体积，现在给定每个骨头沿途的价值，你能计算出骨头收集者能获得的最大总价值吗？

输入

第一行包含一个整数T，表示案例的数量。
接下来是T个案例，每个案例有三行，第一行包含两个整数N，V，(N <= 1000, V <= 1000)表示骨头的数量和他的袋子的容积。第二行包含N个整数，表示每个骨头的价值。第三行包含N个整数，表示每个骨头的体积。

输出

每行一个整数，表示最大的总价值（这个数字将小于2^31）。

测试样例

输入

1
5 10
1 2 3 4 5
5 4 3 2 1

输出

14

解释:

• 前5个物品价值分别为1, 2, 3, 4, 5，体积分别为5, 4, 3, 2, 1。
• 最大总价值为14，可以通过选择体积为1、2、3、4的物品实现。

这个问题是一个经典的“0/1背包问题”，可以使用动态规划来解决。我们需要计算每个案例中骨头收集者能够获得的最大总价值。以下是详细的步骤和代码实现。

代码

import java.util.Scanner;
//骨头收集者
public class Main{
	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<N;i++) {
				values[i] = sc.nextInt();//为每个物品依次读入价值
			}
			for(int i= 0;i<N;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<=N;i++) {
			for(int j = 0;j<=V;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];
	}

}

详解

初步思路

通过动态规划解决0/1背包问题，逐步计算每个物品在不同容量下的最大价值。

具体步骤

1. 输入读取:

   • 首先读取案例数量T。
   • 对于每个案例，读取骨头数量N和背包容量V。
   • 读取每个骨头的价值数组values和体积数组volumes。

2. 初始化DP表:

   • 创建一个二维数组dp，其中dp[i][j]表示前i个骨头在背包容量不超过j时的最大总价值。
   • 初始化dp数组为0，因为当没有物品或者容量为0时，最大价值为0。

3. 填充DP表:

   • 遍历所有骨头，从第1个到第N个。
   • 对于每个骨头，从容量0到容量V，逐步更新dp表。
   • 更新规则：
     • 如果不选第i个骨头，dp[i][j] = dp[i-1][j]。
     • 如果选第i个骨头，dp[i][j] = max(dp[i][j], dp[i-1][j-volumes[i-1]] + values[i-1])。

4. 输出结果:

   • 最后，dp[N][V]即为前N个骨头在容量为V时的最大总价值。
   • 对于每个案例，输出对应的最大总价值。

总结方法

动态规划是一种有效解决0/1背包问题的方法，通过构建和填充dp表，我们可以在多项式时间内求解该问题。此方法的关键在于理解和正确应用状态转移方程：在每一步都决定是否选择当前物品，从而保证最大总价值的累积。