0%

【算法学习】01背包与完全背包(dp)

01背包: 每件物品只能取一次
完全背包: 每件物品可以取无限次

01背包

题目链接: AcWing 2. 01背包问题

题目描述:

N 件物品和一个容量是 V 的背包。每件物品只能使用一次

i 件物品的体积是 v[i],价值是 w[i]

求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。

题目分析

  • 状态表示:
    • f[i][j]: 只从前i件物品中选, 且总体积<=j的最大价值
  • 状态划分
    • 以选不选第i件物品划分
    • 不选第i件物品: f[i][j] = f[i - 1][j]
    • 选第i件物品:
      • 前提: 需要j >= v[i]才能把第i件物品放入背包
      • 选了第i件物品,背包的容量j需要减掉v[i]
      • f[i][j] = f[i - 1][j - v[i]] + w[i]
  • 状态计算:
    • f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i])

代码:

C++ 代码

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
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010;

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

int main()
{
// n表示n件物品, m表示背包容量
cin >> n >> m;

// 状态转移方程中用到了i - 1, 所以i从1开始
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 ++)
{
// 状态转移: 背包的容量大于物品的体积的时候才有可能选第i件物品
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;
}

优化空间复杂度

一般是对对动态规划的代码或计算方程做等价变形

01背包的动态转移方程: f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i])f[i]的状态只用到了第f[i - 1]的状态

可以使用滚动数组更新第i层的状态

新的状态转移方程: for(int j = m; j >= v[i]; j--) f[j] = max(f[j], f[j - v[i]] + w[i])

要注意的是01背包的j要从大到小遍历, f[j - v[i]] 的值才会是f[i - 1][j - v[i]] + w[i]的值

从小到大遍历的话更新f[j] 的时候 f[j - v[i]] 已经被刷新掉了

优化后的代码

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<iostream>
#include<algorithm>

using namespace std;

const int N = 1010;

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

int main()
{
// n表示n件物品, m表示背包容量
cin >> n >> m;

// 状态转移方程中用到了i - 1, 所以i从1开始
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]和f[j - v[i]]都是i - 1时更新的
f[j] = max(f[j], f[j - v[i]] + w[i]);
}

cout << f[m] << endl;
return 0;
}

Python版:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def main():
n, m = [int(x) for x in input().split()]
v, w, f = [0] * (n + 1), [0] * (n + 1), [0] * (m + 1)

for i in range(1, n + 1):
v[i], w[i] = [int(x) for x in input().split()]

for i in range(1, n + 1):
for j in range(m, v[i] - 1, -1):
f[j] = max(f[j], f[j - v[i]] + w[i])

print(f[m])


main()

01背包的简单应用

打怪兽

腾讯的一道笔试题

小Q打算穿越怪兽谷,他不会打怪,但是他有钱
他知道,只要给怪兽一定的金币,怪兽就会一直护送着他出谷。
在谷中,他会依次遇见N只怪兽,每只怪兽都有自己的武力值和要贿赂它所需的金币数。
如果小Q没有贿赂某只怪兽,而这只怪兽武力值又大于护送他的怪兽武力之和,这只怪兽就会攻击他。
小Q想知道,要想成功穿越怪兽谷而不被攻击,他最少要准备多少金币。

输入格式

1
2
3
第一行包含整数N,表示怪兽的数量。
第二行包含N个整数d1,d2,…,dn,表示每只怪兽的武力值。
第三行包含N个整数p1,p2,…,pn,表示收买N只怪兽所需的金币数。

输出格式

1
输出一个整数,表示所需最小金币数。

数据范围

1
2
3
1≤N≤50
1≤d[i]≤10^12,
1≤p[i]≤2

输入样例1:

1
2
3
3
8 5 10
1 1 2

输出样例1:

1
2

输入样例2:

1
2
3
4
1 2 4 8
1 2 1 2

输出样例2:

1
6

说明

对于第i只怪兽, 可以选择贿赂或者不贿赂, 当前的战斗力小于怪兽的战斗力时, 只能选择贿赂收买怪兽。

  • 状态表示:
    • f[i][j]表示花到第i只怪兽处花j金币小Q能达到的最大战斗力
  • 状态计算:
    • 不收买怪兽
      • 前提: 当前战斗力比怪兽高, 即 f[i - 1][j] >= d[i]
      • f[i][j] = f[i - 1][j]
    • 收买怪兽:
      • 前提: j >= p[i] 且 花j - d[i]的金币能走到第i只怪兽处即j >= p[i] && f[i - 1][j - p[i]] >= d[i - 1]
      • f[i][j] = f[i - 1][j - d[i]] + p[i]
  • 答案:f[n][i] > 0 的最小的i

代码

C++: 注意数据范围会爆int;

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
35
36
37
38
39
40
41
42
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 110;

int n;
long long d[N], p[N];
long long f[N][2 * N];

int main()
{
cin >> n;
for(int i = 1; i <= n; i ++) cin >> d[i];
for(int i = 1; i <= n; i ++) cin >> p[i];

// 第1只怪兽是一定要买的
for(int i = p[1]; i <= 2 * n; i ++) f[1][i] = d[1];

// 2 * n 是要花的金币的最大值
for(int i = 2; i <= n; i ++)
for(int j = 0; j <= 2 * n; j ++)
{
// 战斗力比怪兽高可以不买这只怪兽
if(f[i - 1][j] >= d[i]) f[i][j] = f[i - 1][j];

// 买的起第i只怪兽, 要看买还是不买划算
if(j >= p[i] && f[i - 1][j - p[i]] >= d[i - 1]) f[i][j] = max(f[i - 1][j], f[i - 1][j - p[i]] + d[i]);
}

for(int i = 0; i <= 2 * n; i ++)
{
if (f[n][i] > 0)
{
cout << i << endl;
break;
}
}

return 0;
}

Python代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def main():
n = int(input())
d = [0] + [int(x) for x in input().split()]
p = [0] + [int(x) for x in input().split()]
f = [[0] * (2 * n + 1) for _ in range(n + 1)]

for i in range(p[1], 2 * n + 1):
f[1][i] = d[1]

for i in range(2, n + 1):
for j in range(2 * n + 1):
if(f[i - 1][j] >= d[i]):
f[i][j] = f[i - 1][j]
if(j >= p[i] and f[i - 1][j - p[i]] >= d[i - 1]):
f[i][j] = max(f[i - 1][j], f[i - 1][j - p[i]] + d[i])

for i in range(2 * n + 1):
if(f[n][i] > 0):
return i

print(main())

完全背包问题

完美背包问题每件物品可以选任意件, f[i][j] 表示和01背包问题一样, 背包容量为 j, 只从前 i 件物品中选的最大价值

可以用 k 枚举每件物品选多少件, 状态转移方程就为 f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i] * 1] + w[i], ... f[i - 1][j - v[i] * k] + w[i] * k);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>

using namespace std;

const int N = 1010;

int main(){
int n,m;
int v[N],w[N];
int f[N][N];
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 - v[i] * k] + w[i] * k);
cout << f[n][m] << endl;
return 0;
}

上面的代码时间复杂度为O(n^3):

f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i], f[i - 1][j - v[i]] + 2 * w[i], ... f[i - 1][j - v[i] * k] + w[i] * k);

观察 f[i][j - v] = max(f[i - 1][j - v[i]], f[i - 2][j - v[i] * 2] + w[i], ... f[i - 1][j - v[i] * (k - 1)] + w[i] * (k - 1));

可以惊奇的发现 f[i][j] 从第二项开始到最后一项, 和 f[i][j - v] 的每项都相似且多了 w[i], 所以最后一层的循环可以转化为 f[i][j] = max(f[i - 1][j], f[i][j - v[i])

时间复杂度优化为O(n^2)

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<iostream>

using namespace std;

const int N = 1010;

int n,m;
int f[N][N];
int v[N], w[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 = 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;
}

空间复杂度也可以优化为一维:

1
2
3
4
5
6
7
8
9
10
11
12
13
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;
}