【潜意识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();
    }
}

代码解释

1. 输入处理：首先通过Scanner读取物品数量n和背包容量C，然后通过循环输入每个物品的重量和价值。
2. DP数组：使用一个二维数组dp[i][j]表示在前i个物品和容量为j的背包中能获得的最大价值。
3. 状态转移：遍历每个物品，对于每种可能的背包容量j，根据是否将当前物品放入背包，更新dp[i][j]。
4. 输出：最后输出dp[n][C]，即在所有物品和背包容量下能够获得的最大价值。

都挺难的，大家好好消化吧，到时候更新更加详细的教程，方便大家理解。 

动态规划的时间复杂度

该算法的时间复杂度是O(n * C)，其中n是物品的数量，C是背包的容量。空间复杂度也是O(n * C)，主要由dp数组占据。

例子解析

假设有如下输入：

4 5 2 3 3 4 4 5 5 6

这意味着有4个物品，背包容量为5，物品的重量和价值分别为：

使用动态规划的算法，我们可以求得最大价值为7，即选择物品1（重量2，价值3）和物品2（重量3，价值4）放入背包中，背包容量为5，总价值为7。

输出：

7