printsdf's blog
0%

背包问题

发表于 更新于
本文字数： 1.7k 阅读时长 ≈ 2 分钟

01背包

题目描述

image-20250427221733213

输入样例

1
2
3
4
5
4 5
1 2
2 4
3 4
4 5

输出样例：

1
8

分析

d6ff6b08f112cec54b1101aecc6d5c7

第一版

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
#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

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

int f[N][N];

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 = 1; j <= m; j ++ )
        {
            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;
}

但是由于f[i][j]的状态转移方程都是由[i-1]层决定，所以第一维实际上可以省略。但是省略之后需要将j倒过来遍历，因为没有降维之前状态转移方程为：

我们需要使用到前一层的$j-v[i]$，所以要保证此时的$j-v[i]$仍然是上一层计算出来的值，而不是$f[i][j-v[i]]$，又因为$j-v[i]$小于$j$，所以只能倒序才能让$j-v[i]$在$j$之后更新。

第二版

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
#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

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

int f[N];

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

完全背包

image-20250427224301479

输入样例

1
2
3
4
5
4 5
1 2
2 4
3 4
4 5

输出样例：

1
10

分析

由于物品可以选无数个，所以我们可以从$0$~$k$个不断尝试，找到最大的价值。

可以写出状态转移方程:

我们还观察到:

所以$f[i][j] = max(f[i-1][j], f[i][j-v[i]])$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

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

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 = v[i]; j <= m; j ++ )
            f[j] = max(f[j], f[j - v[i]] + w[i]);
                
    cout << f[m] << endl;
    return 0;
}

多重背包

基础

数据范围小，普通DP即可

分组背包