当前位置：首页 > news >正文

免费网站备哪里有好看的网站

news 2025/9/18 6:00:31

免费网站备,哪里有好看的网站,网站图片特效代码,东台网站制作目录背包问题简介问题描述输入： 输出： 动态规划解法动态规划状态转移代码实现代码解释动态规划的时间复杂度例子解析输出： 总结作者我蓝桥杯：2023第十四届蓝桥杯国赛C/C大学B组一等奖，所以请听我…

背包问题简介

问题描述

输入：

输出：

动态规划解法

动态规划状态转移

代码实现

代码解释

动态规划的时间复杂度

例子解析

输出：

总结

作者我蓝桥杯：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]，即在所有物品和背包容量下能够获得的最大价值。