学习笔记 背包问题
呵呵侠
2020-08-13 13:07:16
## 1.前置：部分背包
[部分背包问题](https://www.luogu.com.cn/problem/P2240)
理论上讲，部分背包问题不属于背包问题，而属于贪心的问题，但因为后面可能会分析到，~~且名字比较像~~，所以加上了。
```python
题意：
有n种物品，每个物品有它对应的价值和体积。
现在给我一个体积固定的背包，问我可获得的最大价值是多少。
（物品可分割，每种物品只有一个）。
```
其实是一个经典的贪心题，第 $i$ 个物品有一个对应的价值密度 $p_i$ （单位体积的价值），那么只需要把 $p_i$ 排序，然后从最大的 $p_i$ 开始取。
如果当前物品体积 $>$ 背包剩余容量，那么就用背包剩余容量乘上当前物品的单位密度 $p_i$，随后终止程序。
如果物品总体积 $<$ 背包总容量，直接将总价值相加。
代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
int n, m;
int num[1005], price[1005];
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i = i + 1)
cin >> num[i] >> price[i];
for(int i = 1; i <= n; i = i + 1)
for(int j = i + 1; j <= n; j = j + 1)
if(double(double(price[i]) / num[i]) < double(double(price[j]) / num[j]))
{
swap(price[i], price[j]);
swap(num[i], num[j]);
// cout << price[i] << price[j] << endl;
}
int i = 1;
double ans = 0;
while(m > 0)
{
if(num[i] <= m)
{
ans += price[i];
m -= num[i];
}
else if(num[i] > m)
{
ans += (double(price[i]) / num[i]) * m;
break;
}
i = i + 1;
if(i > n)
break;
}
printf("%.2lf", ans);
return 0;
}
```
------------
## 2.01背包
[01背包](https://www.luogu.com.cn/problem/P1048)
刚才的只不过是个热身，重头戏现在才开始：
```python
题意：
有n种物品，每个物品有它对应的价值和体积。
现在给我一个体积固定的背包，问我可获得的最大价值是多少。
（物品不可分割，每种物品只有一个）。
```
感觉是个贪心题，对吗？
贪心确实可以骗分，但并非最优解。
来，我们看一看下面这种情况：
```python
我的背包容量为15，并且有两件物品。
第一件体积为15，价值为15
第二件体积为1，价值为10
```
显然，第一件物品的价值密度 $p_1$ 是 $\dfrac{15}{15} = 1$ ，而第二件物品的价值密度 $p_2$ 是 $\dfrac{10}{1} = 10$ ，显然第二件物品价值密度 $p_2$ 更大，但是显然最优解是选择一件第一种物品。
所以贪心只能骗分，不是最优解。
那么就要请出本文的主角了：$\text{DP}$ ，即为动态规划。
关于动态规划的知识，在[洛谷日报第82期，聊聊动态规划和记忆化搜索](https://www.luogu.com.cn/blog/interestingLSY/memdfs-and-dp)有提到过，在此不多赘述。
~~（自己坑自己的人类迷惑行为）~~
当剩余空间大于当前物品重量时，就有放和不放两种方法，分类讨论，然后取最大值。
动态转移方程就显而易见：$dp_{i,j} = \max(dp_{i - 1,j}, dp_{i - 1,j - weight[i] + value[i]})$，前者是不放的时候的值，后者是放的时候的值，两者取最大为当前的数值。
理论上讲，这道题也可以用递归，但是用递归就会出现大量的重复情况，记忆化也不是特别好写，所以还是写出一个递推。
```cpp
#include <bits/stdc++.h>
using namespace std;
int m, n;
int w[1005], v[1005];
int dp[1005][1005];
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i = i + 1)
cin >> w[i] >> v[i]; // w代表weight是重量，v代表value是价值
for(int i = 1; i <= n; i = i + 1)
for(int j = 1; j <= m; j = j + 1)
{
if(w[i] > j) // 假如当前背包无法装下当前物品
dp[i][j] = dp[i - 1][j]; // 那就不装了
else // 如果装得下
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]); // 动态转移方程，也是重点
}
cout << dp[n][m] << endl;
return 0;
}
// 是可以AC采药这道题的，但是需要把输入顺序颠倒一下，先输入m，再输入n
```
------------
## 3.完全背包
[完全背包](https://www.luogu.com.cn/problem/P1616)
也是很重要的一部分啊！
```python
题意：
有n种物品，每个物品有它对应的价值和体积。
现在给我一个体积固定的背包，问我可获得的最大价值是多少。
（物品不可分割，每种物品有无数个）。
```
这个应该是贪心题了吧。
非也。
贪心确实可以骗分，但并非最优解。
来，我们看一看下面这种情况：
```python
我的背包容量为15，并且有两种物品。
第一件体积为14，价值为29
第二件体积为3，价值为6
```
显然，第一件物品的价值密度 $p_1$ 是 $\dfrac{29}{14} = 2 + \dfrac{1}{14} > 2$ ，而第二件物品的价值密度 $p_2$ 是 $\dfrac{6}{3} = 2$ ，显然第一件物品价值密度 $p_1$ 更大，但是显然最优解是选择五件第二种物品。
也是一个动归，我们来分析一下。
这次每次放下物品之后空间仍然会减少，但是这个物品不会减少啊。
仍然是求放和不放的最大值，不过放下之后空间要减少，但是当前物品不需要切换了。
所以得到了动态转移方程：$dp_{i,j} = \max(dp_{i - 1,j}, dp_{i,j - weight[i] + value[i]})$
代码如下：
```cpp
#include <iostream>
using namespace std;
int n, m, w[1005], v[1005];
int dp[1005][1005];
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i = i + 1)
cin >> w[i] >> v[i]; // w代表weight是重量，v代表value是价值
for(int i = 1; i <= n; i = i + 1)
for(int j = 1; j <= m; j = j + 1)
{
if(w[i] > j) // 假如当前背包无法装下当前物品
dp[i][j] = dp[i - 1][j]; // 那就不装了
else // 如果装得下
dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i]); // 动态转移方程，也是重点
}
cout << dp[n][m];
return 0;
}
```
也有一位数组写法：
```cpp
#include <iostream>
using namespace std;
int n, m, w[1005], v[1005];
int dp[1005];
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i = i + 1)
cin >> w[i] >> v[i];
for(int i = 1; i <= n; i = i + 1)
for(int j = w[i]; j <= m; j = j + 1)
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
cout << dp[m];
return 0;
}
```