0—-1背包是每个物品只有一个
完全背包，每个物品有无数个
多重背包：有多种物品，每个物品有多少个，都是告诉的？？？？
分组背包是每类物品，比如苹果，橘子，香蕉只能选择一个；西红柿，菠菜，土豆只能选一个

一：状态表示和状态计算

• 状态表示

状态表示一句话概括：前i个物品中总体积小于等于j 的各种选法的集合，他存的数是每一种选法的价值的最大值

• 状态计算

班级分数的例子

• 注意状态计算的时候，右边含有i的情况，很有可能由于i 的体积大于j导致右边情况是不存在，对于左边情况是存在的，所以不用担心。

二维的做法

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int f[N][N], w[N], v[N];
int n, m;
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) // i从1开始需要注意，因为f是前i个物品的最大值,前后对应
    {
        cin >> v[i] >> w[i];
    }
    for (int i = 1; i <= n; i++) // 前0个物品没有意义
        for (int j = 1; j <= m; j++) // 背包体积为0也是没有意义
        {
            f[i][j] = f[i - 1][j];
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]); // 一定注意判断
        }
    cout << f[n][m] << endl;
    return 0;
}

一维的优化

这里一点也不理解一维的做法

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int f[N], v[N], w[N];
int n, m;
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i] >> w[i];
    }
    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] << endl;
    return 0;
}

二：完全背包问题

朴素算法：

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int f[N][N], w[N], v[N];
int n, m;
int main()
{
    ios::sync_with_stdio(false) ;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i] >> w[i];
    }
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
            for (int k = 0; k * v[i] <= j; k++)
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + w[i] * k);
    cout << f[n][m] << endl;
    return 0;
}

优化状态转移方程

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int f[N][N], w[N], v[N];
int n, m;
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i] >> w[i];
    }
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
        {
            f[i][j] = f[i - 1][j];
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
        }
    cout << f[n][m] << endl;
    return 0;
}

状态方程一维的优化

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int f[N], v[N], w[N];
int n, m;
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    for (int i = 1; i <= n; i++)
        for (int j = v[i]; j <= m; j++)
        {
           f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    cout << f[m] << endl;
    return 0;
}

最少的硬币数量

三：多重背包问题

暴力做法:

和上面的完全背包类似，就是加了一个s[i]，第三层循环加了一个判断条件，k <= s[i]。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int f[N][N], v[N], w[N], s[N];
int n, m;
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i] >> w[i] >> s[i];
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            for (int k = 0; k <= s[i] && k * v[i] <= j; k++)
            {
                f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + k * w[i]);
            }
    cout << f[n][m] << endl;
    return 0;
}

多重背包的二进制优化.

• 多重背包问题不能像完全背包进行优化，多了后面一项的同时，不能表示简单的f[i - 1, j - v] + w来表示

下面的两个图，意思就是s个第i个物品，可以拆分成多组，便曾0，1背包，因为多个组合随意组合就能凑出0-s的所有的数，时间复杂度就是下面 第三个图，叫做多重背包的二进制优化.

2.

3.

• 多重背包的优化就是利用二进制进行变换，变成01背包问题，一共两步。
• 其实本质就是把第i给物品的s[i]个，二进制压缩成logs个物品，这些个物品的体积和价值都不相同，所以可以看作一个新的物品，然后用01背包问题去解决。 ```cpp

  include

  include

using namespace std;

const int N = 25000;

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

int main() { ios::sync_with_stdio(false); cin >> n >> m; int cnt = 0; // 新数组的 for (int i = 1; i <= n; i++) // 构造01背包 { int k = 1; int a, b, c; cin >> a >> b >> c; while (k <= c) { ++ cnt; v[cnt] = a k; w[cnt] = b k; c -= k; k = 2; } if (c > 0) { cnt ++; v[cnt] = a c; w[cnt] = b * c; } } n = cnt; for (int i = 1; i <= n; i++) // 01背包的解决 for (int j = m; j >= v[i]; j—) f[j] = max(f[j], f[j - v[i]] + w[i]); cout << f[m] << endl; return 0; }

<a name="FXOza"></a>
# 四：分组背包问题
- 如果使用上一层的状态的时候，变成一维的时候，就需要从大倒下到小转换进行枚举，否则用到本层（完全背包）则需要从小到大。因为从大到小，算这个体积的时候，上一个体积还没有计算过，所以存的是上一个体积的状态
![image.png](https://cdn.nlark.com/yuque/0/2021/png/312760/1629277093520-32cc0f49-585b-4281-b0a5-27e59e6010df.png#clientId=u5552a419-41d1-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=400&id=ud975360a&margin=%5Bobject%20Object%5D&name=image.png&originHeight=799&originWidth=1622&originalType=binary&ratio=1&rotation=0&showTitle=false&size=424392&status=done&style=none&taskId=ua91318a2-b569-4964-bcb4-d2c9cec0dc6&title=&width=811)<br />明显可以得到分组背包问题使用了前一个状态。所以转换成一维的时候，就得考虑从大到小的方式遍历。
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int f[N];
int v[N][N], w[N][N], s[N];
int n, m;
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i];
        for (int j = 1; j <= s[i]; j++)
        {
            cin >> v[i][j] >> w[i][j];
        }
    }
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= 0; j--) // 上面已经分析过了，没有>=v[i]因为i是组，体积判断通过if
            for (int k = 0; k <= s[i]; k++)
                if (v[i][k] <= j) f[j] = max(f[j], f[j - v[i][k]] + w[i][k]); // 不能把这里的if放到上面，会导致第三层循环没有遍历完就结束
    cout << f[m] << endl;
    return 0;
}