DP：背包问题----0/1背包问题

❤️❤️❤️❤️❤️博客主页：lyyyyrics❤️❤️❤️❤️❤️

💗背包问题

背包问题（Knapsack Problem）是一类经典的组合优化问题，在计算机科学和数学中有广泛应用。其基本问题是：

• 输入：给定一个容量为 $W$ 的背包和 $n$ 个物品，每个物品 $i$ 有一个重量 $w_i$ 和一个价值 $v_i$。
• 目标：选择若干个物品放入背包，使得总重量不超过背包的容量 $W$，并且总价值最大化。

💛背包问题的变体

1. 0/1 背包问题：每个物品只能选择一次，即要么选中（1）要么不选（0）。
2. 分数背包问题：每个物品可以分割，即可以选择物品的一部分。
3. 多重背包问题：每个物品有多个副本，可以选择多个相同的物品。
4. 多维背包问题：背包有多个限制条件，例如容量和体积等。

🧡0/1 背包问题的数学定义

目标函数：
$$\text{maximize}\sum _{i=1}^n{c}_i\cdot x_i$$
其中，$n$ 表示物品的数量，$c_i$ 表示物品 $i$ 的价值。

约束条件：
$$\sum _{i=1}^n{w}_i\cdot x_i\le C$$
其中，$w_i$ 表示物品 $i$ 的重量，$C$ 表示背包的容量。

其它约束条件：
x i ∈ { 0 , 1 } x_i \in \{0,1\} xi​∈{0,1}
$$i=1,2,3,\dots ,n$$
其中，$x_i$ 表示物品 $i$ 是否被选中。

💚解决背包问题的方法

解决背包问题的方法有很多，包括动态规划、分支定界法、贪心算法（适用于分数背包问题）以及各种近似算法和启发式算法等。

💙例子

假设有一个背包容量为 50 的背包，有以下物品：

物品	重量	价值
1	10	60
2	20	100
3	30	120

目标是选择物品使得总重量不超过 50 且总价值最大化。在这个例子中，最佳选择是选取物品 2 和物品 3，总重量为 50，总价值为 220。

💗解决背包问题的一般步骤？

背包问题是一个经典的优化问题，可以通过动态规划算法来解决。下面是解决背包问题的一般步骤：

1. 确定问题的约束条件：背包的容量限制和物品的重量和价值。

2. 定义状态：将问题拆解为多个子问题，定义状态为背包的容量和可选择的物品。

3. 定义状态转移方程：根据子问题的定义，确定状态之间的关系。例如，对于背包问题，可以定义状态转移方程为f(i,j)，表示在前i个物品中选择，背包容量为j时，可以获得的最大价值。则可以得到状态转移方程：f(i,j) = max(f(i-1,j), f(i-1,j-w[i])+v[i])，其中w[i]和v[i]分别表示第i个物品的重量和价值。

4. 确定初始条件：确定边界条件，即背包容量为0时，价值为0。

5. 通过动态规划算法计算最优解：根据状态转移方程和初始条件，利用循环或递归的方式计算最优解。

6. 回溯最优解：根据计算得到的最优解，可以通过回溯的方式确定选择了哪些物品放入背包中，从而得到最终的解。

需要注意的是，背包问题的解决方法还包括贪心算法、分支界限算法等。具体选择哪种方法取决于问题的约束条件和需要优化的目标。

💗例题

题目链接
题目：

样例输出和输入：

这道题并不是leetcode的那种接口的模式，而是ACM模式，我们需要进行完整的输入和输出，我们先分析第一个样例：

0	1	2	3
容量	2	4	1
价值	10	5	4

第一个问题是给定一个背包容量，求出当背包的容量不用装满时的最大价值，意思就是我们选出的物品的总的容量可以小于背包的容量，也可以等于背包的容量，这时，我们可以第一个物品和三个物品的价值是最大的。
总价值为14，
第二个问题是我们必须将 背包容量给塞满，求塞满的状态的物品的最大价值，这种情况下有可能是没有结果的，因为无法选出能将背包塞满的组合 ，所以这时候就输出零。但是这个例子是可以输出结果的，塞满的情况应该是第二个物品和第三个物品，总价值是9，所以最后输出14和9。

算法原理：
状态表示：dp[i][j]-----表示选到第i个位置时的所有选法中的不超过总容积j的最大价值。
状态转移方程：
这是不把背包填满的情况下的状态转移方程，还有一个问题就是需要将背包填满。

所以这里如果要用到前一个状态的话，应该判断一下前一个状态是否是-1，如果前一个状态是-1的话，就表示这种情况根本不存在 ，所以不能选择这种状态

初始化：第一个问题的初始化只需要将dp表初始化为0，第二个问题的初始化上面已经讨论过了。
填表顺序：也是按照从左上角到右下角，依次填表。
返回值：返回dp[n][V]
代码展示：

#include <cstring>
#include <iostream>
#include<string>
using namespace std;//数据范围
const int N = 1010;
//n个数据，V为背包的总容量，v表示单个物品的所占容积，w表示单个物品所含的价值
int n, V, v[N], w[N];
//i表示第i个位置，j表示总的容积
int dp[N][N];int main()
{//输入总数据，和总容积cin >> n >> V;for (int i = 1;i <= n;i++){cin >> v[i] >> w[i];}//解决第一问for (int i = 1;i <= n;i++){//j表示容量for (int j = 1;j <= V;j++){//不选的情况dp[i][j] = dp[i - 1][j];//如果能选，则和之前不选的情况求一个maxif (j >= v[i])dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);}}//输出最后一个dp状态cout << dp[n][V] << endl;//重置dp表，将表中数据重置为0memset(dp, 0, sizeof dp);//单独初始化第一排的后面的位置，因为如果没有任何物品根本不可能有价值，所以初始化为-1for (int i = 1;i <= V;i++){//初始化不存在dp的位置dp[0][i] = -1;}for (int i = 1;i <= n;i++){//j表示容量for (int j = 1;j <= V;j++){//可以不选dp[i][j] = dp[i - 1][j];//如果要选择当前位置的话需要考虑前一个状态是否是-1，选不到的情况 if (j >= v[i] && dp[i - 1][j - v[i]] != -1)dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);}}//如果不存在选满的情况，直接返回0，否则返回dp[n][V]位置的值cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;return 0;
}

代码优化：
可以利用滚动数组进行优化：

#include <cstring>
#include <iostream>
#include<string>
using namespace std;//数据范围
const int N = 1010;
//n个数据，V为背包的总容量，v表示单个物品的所占容积，w表示单个物品所含的价值
int n, V, v[N], w[N];
//i表示第i个位置，j表示总的容积
int dp[N];int main()
{//输入总数据，和总容积cin >> n >> V;for (int i = 1;i <= n;i++)cin >> v[i] >> w[i];//解决第一问for (int i = 1;i <= n;i++)//j表示容量for (int j = V;j >= v[i];j--)//修改遍历顺序//如果能选，则和之前不选的情况求一个maxdp[j] = max(dp[j], dp[j - v[i]] + w[i]);//输出最后一个dp状态cout << dp[V] << endl;//重置dp表，将表中数据重置为0memset(dp, 0, sizeof dp);//单独初始化第一排的后面的位置，因为如果没有任何物品根本不可能有价值，所以初始化为-1for (int i = 1;i <= V;i++)//初始化不存在dp的位置dp[i] = -1;for (int i = 1;i <= n;i++)//j表示容量for (int j = V;j >= v[i];j--)//修改遍历顺序//如果能选，则和之前不选的情况求一个maxif(dp[j-v[i]]!=-1)dp[j] = max(dp[j], dp[j - v[i]] + w[i]);//如果不存在选满的情况，直接返回0，否则返回dp[n][V]位置的值cout << (dp[V] == -1 ? 0 : dp[V]) << endl;return 0;
}

运行结果：

💗总结

通过对0/1背包问题的分析和动态规划解法的详细讲解，我们可以看到这种经典问题在算法设计中的重要性。0/1背包问题不仅是许多实际应用的基础，也是理解和掌握动态规划思想的一个重要实例。

在解决0/1背包问题时，关键在于构建状态转移方程并合理使用空间和时间资源。通过递归和迭代的方法，我们能更好地理解背包问题的解法，优化算法效率，并提升解决复杂问题的能力。

希望这篇博客能帮助你理解0/1背包问题的基本原理和解法，同时激发你对动态规划和算法设计的进一步兴趣和探索。未来的学习中，不妨尝试更多的变种背包问题和动态规划问题，以不断提升自己的算法技能和编程水平。