目录
作者我蓝桥杯：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
编辑
编辑
