学习笔记 背包问题

· · 个人记录

1.前置：部分背包

部分背包问题

理论上讲，部分背包问题不属于背包问题，而属于贪心的问题，但因为后面可能会分析到，且名字比较像，所以加上了。

题意：
有n种物品，每个物品有它对应的价值和体积。
现在给我一个体积固定的背包，问我可获得的最大价值是多少。
（物品可分割，每种物品只有一个）。

其实是一个经典的贪心题，第 i 个物品有一个对应的价值密度 p_i （单位体积的价值），那么只需要把 p_i 排序，然后从最大的 p_i 开始取。

如果当前物品体积 > 背包剩余容量，那么就用背包剩余容量乘上当前物品的单位密度 p_i，随后终止程序。

如果物品总体积 < 背包总容量，直接将总价值相加。

代码：

#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背包

刚才的只不过是个热身，重头戏现在才开始：

题意：
有n种物品，每个物品有它对应的价值和体积。
现在给我一个体积固定的背包，问我可获得的最大价值是多少。
（物品不可分割，每种物品只有一个）。

感觉是个贪心题，对吗？

贪心确实可以骗分，但并非最优解。

来，我们看一看下面这种情况：

我的背包容量为15，并且有两件物品。
第一件体积为15，价值为15
第二件体积为1，价值为10

显然，第一件物品的价值密度 p_1 是 \dfrac{15}{15} = 1 ，而第二件物品的价值密度 p_2 是 \dfrac{10}{1} = 10 ，显然第二件物品价值密度 p_2 更大，但是显然最优解是选择一件第一种物品。

所以贪心只能骗分，不是最优解。

那么就要请出本文的主角了：\text{DP} ，即为动态规划。

关于动态规划的知识，在洛谷日报第82期，聊聊动态规划和记忆化搜索有提到过，在此不多赘述。

（自己坑自己的人类迷惑行为）

当剩余空间大于当前物品重量时，就有放和不放两种方法，分类讨论，然后取最大值。

动态转移方程就显而易见：dp_{i,j} = \max(dp_{i - 1,j}, dp_{i - 1,j - weight[i] + value[i]})，前者是不放的时候的值，后者是放的时候的值，两者取最大为当前的数值。

理论上讲，这道题也可以用递归，但是用递归就会出现大量的重复情况，记忆化也不是特别好写，所以还是写出一个递推。

#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.完全背包

完全背包

也是很重要的一部分啊！

题意：
有n种物品，每个物品有它对应的价值和体积。
现在给我一个体积固定的背包，问我可获得的最大价值是多少。
（物品不可分割，每种物品有无数个）。

这个应该是贪心题了吧。

非也。

贪心确实可以骗分，但并非最优解。

来，我们看一看下面这种情况：

我的背包容量为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]})

代码如下：

#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;
}

也有一位数组写法：

#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;
}