01背包

01背包题目
在这里插入图片描述
采用一维优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;
// OJ传送门：https://www.dotcpp.com/oj/problem2131.html
// 01背包一维优化
// 特点：每个物品只有一个
#define maxn 10000
int N, M; // N个物品，背包容量M
int value[maxn];
int space[maxn];
int bag[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin >> M >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> space[i] >> value[i];
    }
    for (int i = 1; i <= N; i++) //枚举编号
    {
        for (int j = M; j >= space[i]; j--) //枚举空间(从后往前！)
        {
            bag[j] = max(bag[j - space[i]] + value[i], bag[j]);
        }
    }
    cout << bag[M];
    return 0;
}

完全背包

完全背包题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;
// OJ传送门：https://www.dotcpp.com/oj/problem2131.html
// 完全背包(一维优化)
// 特点：每个物品数量无限
#define maxn 100000
int N, M; // N个物品,M空间
int value[maxn];
int space[maxn];
int bag[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin >> M >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> space[i] >> value[i];
    }
    for (int i = 1; i <= N; i++)
    {
        for (int j = space[i]; j <= M; j++) //从前往后遍历！
        {
            bag[j] = max(bag[j], bag[j - space[i]] + value[i]);
        }
    }
    cout << bag[M];
    return 0;
}

多重背包

多重背包oj传送门
在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
// OJ传送门：https://www.dotcpp.com/oj/problem2048.html
// 多重背包(一维优化)
// 特点：每个物品有多个，且数量有限且给出
#define maxn 10000
int N, M;
int value[maxn];
int space[maxn];
int bag[maxn];
int cnt[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
    {
        cin >> space[i] >> value[i] >> cnt[i];
    }
    for (int i = 1; i <= N; i++)
    {
        for (int j = M; j >= 0; j--)
        {
            for (int k = 0; k <= cnt[i]; k++) //多一个次数循环
            {
                if (j - k * space[i] < 0)
                    continue; //写break也行
                bag[j] = max(bag[j], bag[j - k * space[i]] + k * value[i]);
            }
        }
    }
    cout << bag[M];
    return 0;
}

解释

  • 三种背包问题我用的都是一维优化
  • 大家有没有发现，01背包和完全背包的唯一区别就是j(空间)一个是从头开始循环，而另外一个则是恰恰相反，其实道理很简单：01背包考虑每个物品只用一次，它实际上转移方程是和i未选上之前的此时j进行比较，所以我们从后往前循环，（因为j-space[i]的值肯定比我们的j小，所以保证i只用一次），而完全背包相反，我们从头开始循环，因为i物品可以反复使用，所以j-space[i]在j的循环范围内，如果满足条件还可以继续使用
  • 多重背包可以转化为01背包问题（将第i个物品作为n个相同物品计入物品总数中）