背包问题

背包问题

  • 背包问题是一类经典的优化问题，在计算机科学中有广泛的应用。
  • 简而言之，背包问题是在有限的背包容量内，如何最大化物品的价值和数量的问题。
  • 具体来说，给定一组物品，每个物品有确定的重量和价值，需要选择一些物品放入背包中，使得它们的总重量不超过背包容量，同时总价值最大化。
  • 背包问题有多种不同的变种，包括 0/1 背包、完全背包和多重背包等。

0/1背包问题

0/1背包问题是指在有限的容量下，选择某些物品放入背包，每个物品的体积和价值不尽相同，而目标是在不超过背包容量的情况下，让背包所装物品的总价值最大。其中，0/1表示每个物品只能选择装入一次或不装。

二维解法

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 = 10010;

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

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    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 - 1][j - v[i]] + w[i]);
        }
    }
    int res = 0;
    for (int i = 0; i <= m; i ++){
        res = max(res, f[n][i]);
    }
    cout << res;
    return 0;
}

直接输出结果最大为f[n][m]

因为在 j 的循环中，j 是从 m 开始递减到 v[i]。所以，将最大价值记录在 f[n][m] 中即可。当背包容量为 m 时，已经遍历了所有的物品，得到了所有的状态，因此此时 f[n][m] 就是背包在容量为 m 时的最大价值。

一维优化

将状态f[i][j]优化到一维f[j]，实际上只需要做一个等价变换。

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 = 10010; 
 
int n, m; 
int f[N]; 
int v[N], w[N]; 
 
int main(){ 
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); 
    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]; 
    return 0; 
}

在以上代码中，使用了动态规划算法来解决 0/1 背包问题。其中，在计算循环 j 时，使用了状态转移方程：f[j] = max(f[j], f[j - v[i]] + w[i])，表示将第 i 件物品放入背包之后，容量为 j 时的最大价值。

完全背包问题

  • 完全背包问题是指在有限的容量下，选择某些物品放入背包，每个物品的体积和价值不尽相同，而目标是在不超过背包容量的情况下，让背包所装物品的总价值最大。与 0/1 背包问题不同的是，每个物品的数量都是无限的，可以选择多次放入，因此也称为多重背包问题。
  • 对于完全背包问题，同样可以使用动态规划算法进行求解。在计算 f[i][j](表示前 i 种物品，总体积不超过 j，所能获得的最大价值) 时，使用的状态转移方程是：f[i][j] = max(f[i - 1][j - k * v[i]] + k * w[i])，其中 k 是 0 到 j/v[i] 中的整数，表示选择放入 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 = 10010;

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

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    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];
    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
29
30
31
32
#include <bits/stdc++.h>
using namespace std;

const int N = 10010;

int f[N];
int n, m;

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ){
        int v, w, s;
        cin >> v >> w >> s;
        int k = 1;  //二进制优化
        while(k <= s){ 
            for(int j = m; j >= v * k; j --){
                f[j] = max(f[j], f[j-v * k] + w * k);
            }

            s -= k;
            k <<= 1;    //优化内容

        }
        if(s){   //判断是否二进制分完，如果没有，继续分下面的
            for(int j = m; j >= v * s; j --){
                f[j] = max(f[j], f[j-v * s] + w * s);
            }
        }
    }
    cout << f[m] << endl;
    return 0;
}
  • 与完全背包问题相同，我们可以使用二进制优化来优化多重背包问题。与完全背包问题不同的是，我们需要将一个物品拆分成若干个物品，每个物品的重量和价值是原物品的重量和价值的k倍。这样，在一个物品组合的过程中，我们只需要使用O(W)的时间和空间，从而将时间复杂度优化到O(nW)。