算法 — 背包问题详解

正文之前提供了两个背包问题的各种运用供大家学习

经典class="superseo">class="superseo">算法之背包求最大最小值问题
经典算法之背包计数问题

01背包问题

输入

4 5
1 2
2 4
3 4
4 5

输出

8

题解

核心思路

1. 矩阵 f 初始化为全零，这样可以保证只要体积不超过 j 都能装入
f[i][j] : 即从前 i 个物品中选，总体积不超过 j 的方案数。
f[i - 1][j - v] 表示： 当前为要处理的物品 i， 当满足 j >= v 时， 当前物品可以装入，
计算装入后是否会使得总价值变大，所以需要从之前的 i - 1, j - v, 转移过来用来代表 f[i][j]

当背包容量够时：
选：f[i][j] = f[i - 1][j - v[i]] + w[i]。
不选：f[i][j] = f[i - 1][j] 。
最终取对两者取max

可以打印出来看下结果：
装入前一个物品的结果（1 2）：0 2 2 2 2 2 
装入前一个物品的结果（2 4）：0 2 4 6 6 6 
装入前一个物品的结果（3 4）：0 2 4 6 6 8 
装入前一个物品的结果（4 5）：0 2 4 6 6 8 

朴素解法

#include 
using namespace std;

const int N = 1010;

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

int main() {
    
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++ ) {
        int v, w;
        cin >> v >> w;
        for (int j = 0; j <= m; j ++ ) {
            f[i][j] = f[i-1][j];
            if (j >= v) f[i][j] = max(f[i][j], f[i - 1][j - v] + w); 
        }
    }
    
    cout << f[n][m];
    return 0;
}

状态压缩

代码简述：
利用滚动数组，即所以物品放于一维的空间上 *** 作，当需要由上一状态转移过来了，为了不破坏前一阶段的数据，所以需要注意，j 从 m ~ v, 而 小于 v 的部分即为不选，不需要做任何 *** 作，直接从上一状态转移过来即可

#include 
using namespace std;

const int N = 1010;

int n, m;
int f[N];

int main() {
    
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++ ) {
        int v, w;
        cin >> v >> w;
        for (int j = m; j >= v; j -- ) {
            f[j] = max(f[j], f[j - v] + w); 
        }
    }
    
    cout << f[m];
    
    return 0;
}

完全背包

输入

4 5
1 2
2 4
3 4
4 5

输出

10

题解

类比 01 背包问题，完全背包满足在体积不超过 j 的情况下 可以装无限个，所以可以通过去判断所有可能的情况，来判断价值的最大值

朴素解法

#include 
using namespace std;

const int N = 1010;

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

int main() {
    
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++ ) { //依次加入每个背包
        int v, w;
        cin >> v >> w;
        for (int j = 0; j <= m; j ++ ) { // 依次计算 子状态
            for (int k = 0; k * v <= j; k ++ ) //循环判断再满足体积不超过 j 的情况下价值最大
                f[i][j] = max(f[i][j], f[i-1][j - k * v] + k * w); //这里不需要特判不装的时候， 因为当k = 0 时，即为不装的情况。
        }
    }
    
    
    cout << f[n][m];
    
    
    return 0;
}

状态压缩

思路（非常经典）

f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w ,  f[i-1,j-2*v]+2*w , f[i-1,j-3*v]+3*w , .....)
f[i , j-v]= max(            f[i-1,j-v]   ,  f[i-1,j-2*v] + w , f[i-1,j-3*v]+2*w , .....)
由上两式，可得出如下递推关系： 
                        f[i][j]=max(f[i,j-v] + w , f[i-1][j])  //即选与不选两种状态

注意完全背包问题再转换为一维时， j 从 v ~ m ，由推导式可以看出，f[i][j] 是基于当前的状态，而不是上一状态转移过来，就得使劲污染

#include 
using namespace std;

const int N = 1010;

int n, m;
int f[N];

int main() {
    
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++ ) { //依次加入每个背包
        int v, w;
        cin >> v >> w;
        for (int j = v; j <= m; j ++ ) { 
            f[j] = max(f[j], f[j - v] + w);
        }
    }
    
    
    cout << f[m];
    
    
    return 0;
}

多重背包问题

输入

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

输出

10

题解

完全背包问题的特殊形式，每个物品不能超过 s 件

朴素版

#include 
using namespace std;

const int N = 110;

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

int main() {
    
    cin >> n >> m;
    
    for (int i = 1; i <= n;  i++ ) {
        int v, w, s;
        cin >> v >> w >> s;
        for (int j = 0; j <= m; j ++ ) {
            for (int k = 0; k * v <= j && k <= s; k ++ ) {
                f[i][j] = max(f[i][j], f[i - 1][j - k * v] + k * w);
            }
        }
    }
    
    cout << f[n][m];
    
    
    return 0;
}

二进制优化

这里奉上大佬的优化讲解 ： 二进制优化多重背包的思路

#include 
using namespace std;

const int N = 2010;
typedef pair<int, int> PII;

int n, m;
int f[N];

vector<PII> G;

/*
    首先可以利用每个物品分成 s 份，跑 01 背包， 但是会超时
    进一步优化利用二进制来表示物品个数：
    例如： 14 ： 1 2 4 7   
           6  ： 1 2 3 
    可以看出最后一个特殊处理，不能超出所要表达的物品个数


*/


int main() {
    
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++ ) {
        int v, w, s;
        cin >> v >> w >> s;
        for (int k = 1; k <= s; k *= 2) {
            s -= k;
            G.push_back({k * v, k * w});
        }
        if (s > 0) G.push_back({s * v, s * w}); //把最后剩余的部分装入进去;
    }
    
    
    //利用上述就可以跑 01 背包模型啦
    
    for (int i = 0; i < G.size(); i ++ ) {
        int v = G[i].first, w = G[i].second;
        for (int j = m; j >= v; j -- ) {
            f[j] = max(f[j], f[j - v] + w);
        }
    }
    
    cout << f[m];
    
    
    return 0;
}

分组背包问题

输入

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

输出

8

题解

同 01 背包问题，只需遍历每一组的每一个物品，每次都将每种状态保存起来，最终选择出最大的价值

#include 
using namespace std;

const int N = 110;

int n, m;

int f[N][N], s[N], v[N][N], w[N][N];

int main() {
    
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++ ) {
        cin >> s[i];
        for (int j = 1; j <= s[i]; j ++ ) {
            cin >> v[i][j] >> w[i][j];
        }
    }
    
    
    for (int i = 1; i <= n; i ++ ) { //遍历每一组
        for (int j = 0; j <= m; j ++ ) { 
            for (int k = 0; k <= s[i]; k ++ ) { //遍历组内的每一个物品
                /* 这里的条件一定要写下来，不能放在 k 的判断里面。
                   如果放上去，只要第一个物品不满足则跳出 for 循环，
                   而后面的物品可能有满足条件的。
                */
                if (j >= v[i][k]) f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
            }
        }
    }
    
    cout << f[n][m];
    
    return 0;
}

状态压缩

#include 
using namespace std;

const int N = 110;

int n, m;

int f[N], s[N], v[N][N], w[N][N];

int main() {
    
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++ ) {
        cin >> s[i];
        for (int j = 1; j <= s[i]; j ++ ) {
            cin >> v[i][j] >> w[i][j];
        }
    }
    
    
    for (int i = 1; i <= n; i ++ ) {
        for (int j = m; j >= 0; j -- ) {
            for (int k = 0; k <= s[i]; k ++ ) {
                /* 这里的条件一定要写下来，不能放在 k 的判断里面。
                   如果放上去，只要第一个物品不满足则跳出 for 循环，
                   而后面的物品可能有满足条件的。
                */
                if (j >= v[i][k]) f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
            }
        }
    }
    
    cout << f[m];
    
    return 0;
}