【潜意识Java】蓝桥杯算法有关的动态规划求解背包问题
目录
背包问题简介
问题描述
输入:
输出:
动态规划解法
动态规划状态转移
代码实现
代码解释
动态规划的时间复杂度
例子解析
输出:
总结
作者我蓝桥杯:2023第十四届蓝桥杯国赛C/C++大学B组一等奖,所以请听我讲:
蓝桥杯是一项备受推崇的编程比赛,参赛者需要通过高效的算法解决各种具有挑战性的问题。今天,我们将深入探讨蓝桥杯经典算法题目之一——0/1背包问题。通过这个题目,我们不仅可以学习如何高效使用动态规划,还能够更好地掌握如何在实际问题中应用算法思想。
背包问题简介
🍎背包问题的核心思想是:给定一组物品,每个物品有一个重量和一个价值,现在有一个背包,背包的容量有限,问如何选择物品放入背包,使得在不超过背包容量的情况下,物品的总价值最大。🍊
应该也很要理解,就是这么个道理:
🍏在0/1背包问题中,每个物品只能选择放入背包一次,要么放入背包,要么不放入。🍏
问题描述
那我们假设我们有一个背包,他的容量为C
,有n
个物品。其中每个物品有一个重量wi
和一个价值vi
。我们需要在这些物品中选择若干个物品放入背包,使得背包中物品的总价值最大,并且物品的总重量不超过背包的容量。就是这个问题。
输入:
- 第1行:
n
和C
,表示物品的数量和背包的容量。- 第2至n+1行:每行包含两个整数
wi
和vi
,分别表示第i个物品的重量和价值。输出:
- 输出一个整数,表示在不超过背包容量的前提下,能够获得的最大价值。
动态规划解法
是一种通过将复杂问题分解成子问题来求解的方法。在背包问题中,我们可以定义一个二维数组dp[i][j]
,表示前i
个物品中能够在容量为j
的背包中获得的最大价值。
动态规划状态转移
- 如果第
i
个物品不放入背包,那么dp[i][j] = dp[i-1][j]
,即最大价值与不放入这个物品时的最大价值相同。🥞🥞🥞🥞- 如果第
i
个物品放入背包,那么dp[i][j] = dp[i-1][j-wi] + vi
,即最大价值为放入该物品后,剩余容量所能获得的最大价值。🍔🍔🍔🍔🍔
最终,我们要求解的是dp[n][C]
,即在n
个物品和背包容量C
下,能够获得的最大价值。
代码实现
import java.util.Scanner;
public class Knapsack {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 输入物品数量和背包容量
int n = sc.nextInt();
int C = sc.nextInt();
// 定义物品的重量和价值
int[] weight = new int[n + 1];
int[] value = new int[n + 1];
// 输入每个物品的重量和价值
for (int i = 1; i <= n; i++) {
weight[i] = sc.nextInt();
value[i] = sc.nextInt();
}
// dp数组,dp[i][j]表示前i个物品,背包容量为j时的最大价值
int[][] dp = new int[n + 1][C + 1];
// 动态规划求解
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= C; j++) {
if (j >= weight[i]) {
// 如果当前物品可以放入背包,则选择放与不放的最大值
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
} else {
// 当前物品不能放入背包时,最大价值与不放当前物品时相同
dp[i][j] = dp[i - 1][j];
}
}
}
// 输出最大价值
System.out.println(dp[n][C]);
sc.close();
}
}
代码解释
- 输入处理:首先通过
Scanner
读取物品数量n
和背包容量C
,然后通过循环输入每个物品的重量和价值。- DP数组:使用一个二维数组
dp[i][j]
表示在前i
个物品和容量为j
的背包中能获得的最大价值。- 状态转移:遍历每个物品,对于每种可能的背包容量
j
,根据是否将当前物品放入背包,更新dp[i][j]
。- 输出:最后输出
dp[n][C]
,即在所有物品和背包容量下能够获得的最大价值。
都挺难的,大家好好消化吧,到时候更新更加详细的教程,方便大家理解。
动态规划的时间复杂度
该算法的时间复杂度是
O(n * C)
,其中n
是物品的数量,C
是背包的容量。空间复杂度也是O(n * C)
,主要由dp
数组占据。
例子解析
假设有如下输入:
4 5 2 3 3 4 4 5 5 6
这意味着有4个物品,背包容量为5,物品的重量和价值分别为:
物品 | 重量 | 价值 |
---|---|---|
1 | 2 | 3 |
2 | 3 | 4 |
3 | 4 | 5 |
4 | 5 | 6 |
使用动态规划的算法,我们可以求得最大价值为7,即选择物品1(重量2,价值3)和物品2(重量3,价值4)放入背包中,背包容量为5,总价值为7。
输出:
7