0%

【算法学习】01背包与完全背包（dp）

发表于
本文字数： 3.7k 阅读时长 ≈ 3 分钟

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][j - v[i]] + w[i]
  • 状态计算:
    • f[i][j] = max(f[i - 1][j], f[i][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())

完全背包问题