背包问题

01背包#

题目描述#

输入样例

输出样例：

1
8

分析#

第一版#

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
const int N = 1010;
6

7
int n, m;
8
int v[N], w[N];
9

10
int f[N][N];
11

12
int main()
13
{
14
    cin >> n >> m;
15

16
    for (int i = 1; i <= n; i ++ )   cin >> v[i] >> w[i];
17

18
    for (int i = 1; i <= n; i ++ )
19
        for (int j = 1; j <= m; j ++ )
20
        {
21
            f[i][j] = f[i - 1][j];
22
            if (j >= v[i])
23
              f[i][j] = max(f[i][j], f[i-1][j - v[i]] + w[i]);
24
        }
25

26
    cout << f[n][m] << endl;
27

28
    return 0;
29
}

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

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

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

第二版#

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
const int N = 1010;
6

7
int n, m;
8
int v[N], w[N];
9

10
int f[N];
11

12
int main()
13
{
14
    cin >> n >> m;
15

16
    for (int i = 1; i <= n; i ++ )   cin >> v[i] >> w[i];
17

18
    for (int i = 1; i <= n; i ++ )
19
        for (int j = m; j >= v[i]; j -- )
20
            f[j] = max(f[j], f[j - v[i]] + w[i]);
21

22
    cout << f[m] << endl;
23

24
    return 0;
25
}

完全背包#

输入样例

输出样例：

1
10

分析#

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

可以写出状态转移方程:

f[i][j] = max\{f[i - 1][j - k * v[i]] + k * w[i]\}\\

我们还观察到:

f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]], \cdots,f[i-1][j-k*v[i]]+w[i]*k)\\ f[i][j-v[i]] = max(f[i-1][j-v[i]],\cdots,f[i-1][j-k*v[i]]+w[i]*k)

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

代码#

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
const int N = 1010;
6

7
int n, m;
8
int v[N], w[N];
9
int f[N];
10

11
int main()
12
{
13
    cin >> n >> m;
14
    for (int i = 1; i <= n; i ++ )  cin >> v[i] >> w[i];
15
    for (int i = 1; i <= n; i ++ )
16
        for (int j = v[i]; j <= m; j ++ )
17
            f[j] = max(f[j], f[j - v[i]] + w[i]);
18

19
    cout << f[m] << endl;
20
    return 0;
21
}

多重背包#

基础#

数据范围小，普通DP即可

音乐

Lovely firefly!

音乐