❗❗❗必看:
下列题我全部都使用 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背包问题，逐步计算每个物品在不同容量下的最大价值。
具体步骤
输入读取:
- 首先读取案例数量T。
- 对于每个案例，读取骨头数量N和背包容量V。
- 读取每个骨头的价值数组values和体积数组volumes。
初始化DP表:
- 创建一个二维数组dp，其中dp[i][j]表示前i个骨头在背包容量不超过j时的最大总价值。
- 初始化dp数组为0，因为当没有物品或者容量为0时，最大价值为0。
填充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])。
输出结果:
- 最后，dp[N][V]即为前N个骨头在容量为V时的最大总价值。
- 对于每个案例，输出对应的最大总价值。
总结方法
动态规划是一种有效解决0/1背包问题的方法，通过构建和填充dp表，我们可以在多项式时间内求解该问题。此方法的关键在于理解和正确应用状态转移方程：在每一步都决定是否选择当前物品，从而保证最大总价值的累积。