背包问题

五种背包问题

1、01背包：

描述

从n个物品中选，每个物品只能选一次或者不选，总体积不超过m的情况下，
求总价值最大。

时间复杂度：

​ O(nm)

分析过程：

​ 状态表示：f[i][j]，从前i个物品中选，其总体积不超过j的前提下，所有选法的总价值的最大值
​ 属性：max
​ 状态计算：以最后一个物品是否选择进行划分：
​ （1）不选：f[i][j] = f[i - 1][j];
​ （2）选：if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i])
​ 求方案数时，注意是否需要初始化。
​ 枚举体积一维的时候，注意是从1开始还是0开始，且枚举体积时由于每次用的是上一层的状态，故需要从后往前枚举。

状态转移方程：

f[i][j] = f[i - 1][j];  //不含i的一定存在
           if (j >= v[i]) f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);//只有背包装的下第i个物品时，才存在这种情况

2、完全背包：

描述：

从n个物品中选，每个物品可以选无数次，总体积不超过m的情况下，求总价值的
最大值。

时间复杂度：

O(nm)

分析过程：

状态表示：f[i][j]，从前i个物品中选，其总体积不超过j的前提下，所有选法的总价值的最大值。
属性：max
状态计算：以最后一个物品是否选择划分：
（1）不选：f[i][j] = f[i - 1][j]
（2）选：if (j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);（优化后的状态转移方程）

求方案数时，注意是否需要初始化。
枚举体积一维的时候，注意是从1开始还是0开始，枚举体积时，由于每次用的是本层的状态，故需要从前往后枚举。

状态转移方程：

f[i][j] = f[i - 1][j];
            if (j >= v[i]) f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]);

3、多重背包：

描述：

从n个物品中选，每个物品只能选若干次，总体积不超过m的情况下，求总价值的
最大值。

分析过程：

状态表示：从前i个物品中选，其总体积不超过j的前提下，所有选法的总价值的最大值。
属性：max
状态计算：以最后一个物品是否选择划分：
（1）不选：f[i][j] = f[i - 1][j]
（2）选：由于每个物品可以选k次，故需要另外加一层循环，枚举每个物品选几个。
for (int k = 0; k <= s[i]; k ++) O(n^3)
if (j >= k * v[i]) f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + w[i] * k);

二进制优化：	O(nlogsm)
    将每种物品的k个物品，根据二进制进行打包成新的物品，全部打包后看作01背包做即可，注意此时的物品数量就不再是n了，而需要重新计算，并且需要注意此时的空间可能会爆掉，需要优化成一维数组，在优化的时候，由于每次用到的是上一层的状态，故不能先更新前面的状态，否则会影响结果，故需要从大到小枚举体积。
    这里开数组时，需要多开一些空间，因为重新打包，物品种类就大于了N

最坏情况，每种物品都有2000个，1000个物品，就需要打包成log2 * 1000 = 11000，再加上我们的数组下标是从1开始存的，所以数组空间至少要开11001；

代码模板：

暴力解：
	for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            for (int k = 0; k <= s[i]; k ++)
            {
                if (j >= v[i] * k) f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
            }
二进制优化：     
	#include <iostream>

    using namespace std;

    const int N = 15000;

    int v[N], w[N];
    int f[N];
    int n, m;

    int main()
    {
        cin >> n >> m;  //种数和容量

        int cnt = 0;
        for (int i = 1; i <= n; i ++)
        {
            int a, b, s;    //体积、价值、数量
            cin >> a >> b >> s;

            int k = 1;
            while (k <= s)
            {
                cnt ++;
                v[cnt] = a * k;
                w[cnt] = b * k;
                s -= k;
                k *= 2;
            }
            if (s > 0)
            {
                cnt ++;
                v[cnt] = a * s;
                w[cnt] = b * s;
            }
        }

        n = cnt;        //更新种数
        for (int i = 1; i <= n; i ++)
            for (int j = m; j >= v[i]; j --)
                f[j] = max(f[j], f[j - v[i]] + w[i]);

        cout << f[m];


        return 0;
    }

4、分组背包：

描述：

从n组物品中选，每组物品有若干个，同一组的物品只能选择一个，求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

时间复杂度：

​ O(nms)

分析过程：

集合：从n组物品中选，每组物品有若干个，同一组的物品只能选择一个，在总体积不超过j的情况下，所有选法的价值的最大值。
属性：max
状态计算：以最后一个组是否选择划分：
（1）不选，f[i][j] = f[i - 1][j]
（2）选，由于每组有k个物品，故需要枚举这k个物品
for (int k = 1; k <= cnt[i]; k ++)
if (j >= v[i][k]) f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);

代码模板：

for (int i = 1; i <= n; i ++)   //每组物品
        for (int j = m; j >= 0; j --)  //容量
            for (int k = 1; k <= s[i]; k ++) //枚举所有的选择
                if (v[i][k] <= j)   //只有当容量能装得下，才有选的必要
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);

5、混合背包：

描述：

有 N 种物品和一个容量是 V 的背包。物品有三种，分别是01背包，完全背包，多重背包，求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

分析：

01背包、完全背包、多重背包三种背包问题放在一起，在计算状态的时候，判断是哪种背包，就用哪种状态转移方程即可。

代码模板：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int f[N];

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++)
    {
        int v, w, s;
        cin >> v >> w >> s;
        if (s == 0)     //完全背包
        {
            for (int j = v; j <= m; j ++) f[j] = max(f[j], f[j - v] + w);
        }
        else    //01背包是特殊的多重背包可以一起写，01背包是每种物品只有1件的多重背包
        {
            if (s == -1) s = 1;
            for (int k = 1; k <= s; k *= 2) //二进制优化多重背包，枚举几个物品分成一个新物品
            {
                for (int j = m; j >= k * v; j --)   //枚举每个新物品的体积
                    f[j] = max(f[j], f[j - k * v] + k * w);
                s -= k;
            }

            if (s)
            {
                for (int j = m; j >= s * v; j --)   //将剩余不够分成新物品的物品，分成一组，枚举其体积
                    f[j] = max(f[j], f[j - s * v] + s * w);
            }
        }
    }

    cout << f[m] << endl;

    return 0;
}