无废话版前言（对于这篇分享，神犇们可以【点个栈】走啦~

仅希望本分享对所有OIer的算法之旅有些许帮助

-----（玖^一些专用学习录）

背包类型：

1.01背包问题

2.完全背包问题

3.多重背包问题

4.分组背包问题

5.二维背包

1.01背包问题

问题描述

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

第$i$件物品的体积是$vi$，价值是$wi$。

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

输出最大价值。

输入格式

第一行两个整数，$N$，$V$，用空格隔开，分别表示物品数量和背包容积。

接下来有$N$ 行，每行两个整数 $vi$,$wi$，用空格隔开，分别表示第 $i$ 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

$0<N,V≤1000$

$0<vi,wi≤1000$

输入样例

4 5

1 2

2 4

3 4

4 5

输出样例：

8

分析

对于本题我们不妨记

$$f[i][j]$$

表示只看前$i$个物品，总体积是$j$的情况下，总价值最大是多少？

首先根据题目分析可以知道,每件物品只有不选或者选两种情况,记为$0$和$1$:
$$①f[i][j]=f[i−1][j]$$
$$②f[i][j]=f[i−1][j−v[i]]+w[i]$$
其中第一个式子为不选第$i$个物品,第二个式子为选第$i$个物品。

对每一种情况都进行一次记录其最大值,即

$$f[i][j]=max(①,②)$$
根据以上分析可知
$$result=max(f[n],[0∼V])$$

代码：

#include<bits/stdc++.h>
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-1][j-v[i]]+w[i]);
        }
    int res=0;
    for(int i=0;i<=m;i++) res=max(res,f[n][i]);

    cout<<res<<endl;
    return 0;
}

当然这个题不必把每一层的值都记下来,因此本题使用一维数组来对上面的方法进行优化。

虽说我们并没有将每一层的值都记录下来，但是我们再每一次循环的时候都会将每一行的值进行更新替换。

对此，如果我们还想使用上一行的值的话，只能通过从后往前进行更新了。

so:

#include<bits/stdc++.h>
using namespace std;

const int N=1010;

int n,m;
int f[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=m;j>=v[i];j--){
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }

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

2.完全背包问题

问题描述

有 $N$种物品和一个容量是 $V$ 的背包，每种物品都有无限件可用。

第 $i$ 种物品的体积是 $vi$，价值是 $wi$。

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

输入格式

第一行两个整数，$N$，$V$，用空格隔开，分别表示物品种数和背包容积。

接下来有 $N$ 行，每行两个整数 $vi$,4wi$，用空格隔开，分别表示第$i$ 种物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

$0<N,V≤1000$

$0<vi,wi≤1000$

输入样例

4 5

1 2

2 4

3 4

4 5

输出样例：

10

分析

同01背包,我们不妨记$[i]$表示为总体积是$i$的情况下,最大价值是多少。

其结果为
$$result=max(f[0…m])$$
实际上在01背包中的第二个代码中，我们仅需把第二个循环中的内层循环顺序做修改即可，即:

for(int j=v[i];j<=m;j++)

关于循环反过来正确的证明如下:

1.对于第一个物品考虑来说自然有
$$f[1]=2,f[2]=4,f[3]=6,f[4]=8,f[5]=10$$

显然是正确的

2.假设考虑前$i-1$个物品之后，所有的$f[j]$都是正确的。

3.来证明：在前$i$个物品中,所有的$f[j]$也都是正确的,
不妨固定某一个$j$,如果最优解包含了$k个v[i]$,则一定会在循环内有

$$f[j−k⋅v[i]]=max(f[j−k⋅v[i]],f[j−k⋅v[i]−v[i]]+w[i])$$
且一定会枚举到

$$f[j−k∗v[i]]$$
其中
$$f[j−k∗v[i]]$$
为前$i-1$个物品的值

$$f[j−k∗v[i]−v[i]]$$
为前$i$个物品的值

无论如何,最后都会传递到
$$max(f[v[i]],f[0]+w[i])$$
由2可知
$$f[j]都是正确的⇒f[v[i]]也一定都是正确$$
又:
$$f[0]=0$$
那么
$$w[i]一定正确⇒max(f[v[i],f[0]+w[i]])一定正确⇒f[j−k∗v[i]]一定正确⇒f[j]一定正确$$
以上,得证

代码：

#include<bits/stdc++.h>
using namespace std;

const int N=1010;

int n,m;
int f[N];

int main(){
    cin>>n>>m;
    for(int i=0;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]<<endl;
    return 0;
}

3.多重背包问题(easy)

问题描述

有 $n$ 种物品要放到一个袋子里，袋子的总容量为 $m$，第 $i$ 种物品的体积为 $vi$，把它放进袋子里会获得 $wi$ 的收益，一共有 $li$ 个。问如何选择物品，使得在物品的总体积不超过 $m$ 的情况下，获得最大的收益？请求出最大收益。

数据范围

$$1≤n,m,vi,wi,li≤100$$

分析

第 $i$ 种物品可以使用 $li$ 次， 我们可以把它拆成 $Ii$个物品，每个物品只可以用一次。即转换成01背包问题。

代码:

#include<bits/stdc++.h>
using namespace std;

const int N=1010;

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

int main(){
    cin >> n >> m;
    for(int i = 1;i <= n; i++) cin >> v[i] >> w[i] >> l[i];

    for(int i = 1; i <= n; i++)
        for(int k = 1;k <= l[i];k++)
        for(int j = m; j >= v[i]; j--){
            f[j] = max(f[j],f[j-v[i]] + w[i]);
        }

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

4.多重背包问题(medium)

与easy版本不同的是：该题的数据范围更大了。

问题描述

有 $n$种物品要放到一个袋子里，袋子的总容量为 $m$，第 $i$ 种物品的体积为 $vi$，把它放进袋子里会获得 $wi$ 的收益，一共有 $li$ 个。问如何选择物品，使得在物品的总体积不超过 $m$ 的情况下，获得最大的收益？请求出最大收益。

数据范围

$$1≤n,m,vi,wi,li≤2000$$

分析

通过二进制拆分的方法可以优化本题。

令 $m$ 为最大的 $i$ 满足
$$2i+1−1≤n$$
, 我们从
$$1,2,4,8,16,⋯,2^m,n−2^m+^1+1$$
中选一些数字相加，就可以得出任意$[0,n]$ 内的值，每个数字只能用一次。

引理：从
$$1,2,⋯,2^m$$
中选一些数字相加，可以得出任意
$$[0,2^m+^1)$$
内的值，每个数字只能用一次。

用数学归纳法进行证明：

当 m = 0 的时候显然是成立的；

假设当 m = k 时也成立，也就是从
$$1,2,⋯,2^k$$
中选一些数字相加，可以得出任意
$$[0,2^k+^1)$$
内的值；

不难知道 对
$$[0,2^k+^2)$$
内的值可以从
$$1,2,⋯,2^k$$
中选一些数字相加得到；

也就是说对任意 m = k + 1 也成立。

同样：对于在
$$[2^m+^1,n]$$
内的值，我们取
$$n−2^m+^1+1$$
后，剩下的数字在
$$[2^m+^2−n−1,2^m+^1)$$
内，也可以从
$$1,2,⋯,2^m$$
中选一些数字相加得到。

而通过以上的操作，我们可以把它拆成 $O(log n)$ 个物品，每个物品只能用一次。

代码：

#include<bits/stdc++.h>
using namespace std;

int n, m, f[2001], v[2001], w[2001], l[2001];

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i] >> l[i];
    }
    for(int i = 1; i <= n; i++) {
        int res = l[i];
        for(int k = 1; k <= res; res -= k, k *= 2)
            for(int j = m; j >= v[i] * k; j--)
                f[j] = max(f[j],f[j - v[i] * k] + w[i] * k);

        for(int j = m; j >= v[i] * res; j--)
            f[j] = max(f[j], f[j - v[i] * res] + w[i] * res);
    }
    cout << f[m] << endl;
}

5.多重背包问题(hard)

与easy和medium版本不同的是：该题的数据范围更大了。

问题描述

有 $n$ 种物品要放到一个袋子里，袋子的总容量为$m$，第$i$ 种物品的体积为 $vi$，把它放进袋子里会获得$wi$ 的收益，一共有 $li$ 个。问如何选择物品，使得在物品的总体积不超过$m$的情况下，获得最大的收益？请求出最大收益。

数据范围

$$1≤n,m,vi,wi,li≤10000$$

分析

把考虑了前 $i$ 组物品以后，总体积为 $0~m$ 时的最大收益都记下来。

考虑了前 $i$ 组物品， 总体积为 $j$ 时分成两种情况：

Case 1： 第 $i$ 组物品一个没取，问题就变成了考虑前 $i - 1$ 组物品，总体积为 $j$ 时的情况。

Case 2： 第 $i$ 组物品取了， 我们枚举取了其中的物品$k$ ， 问题变成了考虑了前$i - 1$ 组物品， 总体积为 $j - v_i * k$ 时的情况。

$f[i] [j]$ 表示考虑了前 $i$ 组物品，总体积为 $j$时的最大收益。

需对时间复杂度进行优化

在某一类下标 $k$ 的位置，可以转移到下表在 $[k + 1,k + l_i]$ 中的位置。

那么将 $f[k] - k * w_i$放进单调队列即可。

代码：

#include<bits/stdc++.h>
using namespace std;

int n, m, v, w, t, f[10001], c[10001][2];

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
       cin >> v >> w >> t;
         for(int j = 0; j < v; j++) {
           int k = 0, l = 1;
             for(int p = j, x = 1; p <= m; p += v, ++x){
                 int e = f[p] - x * w, r = x + t;
                 for(; k >= l && c[k][0] <= e; --k);
                     c[++k][0] = e; c[k][1] = r;
                     f[p] = c[l][0] + x * w;
                     for(; k >= l && c[l][1] == x; ++l);
             }
        }
    }
    cout << f[m] << endl;
}

6.分组背包

问题描述

有 $n$ 种物品要放到一个袋子里，袋子的总容量为 $m$。第 $i$ 个物品属于第 $ai$ 组，每组物品我们只能从中选择一个。第 $i$ 种物品的体积为 $vi$，把它放进袋子里会获得 $wi$ 的收益。问如何选择物品，使得在物品的总体积不超过 $m$ 的情况下，获得最大的收益？请求出最大收益。

数据范围：

$$1≤n,m,ai,vi,wi≤1000$$

分析

把考虑了前 $i$ 组物品以后，总体积为 $0~m$ 时的最大收益都记下来。

考虑了前 $i$ 组物品， 总体积为 $j$ 时分成两种情况：

Case 1： 第 $i$ 组物品一个没取，问题就变成了考虑前 $i - 1$ 组物品，总体积为 $j$ 时的情况。

Case 2： 第 $i$ 组物品取了， 我们枚举取了其中的物品 $k$ ， 问题变成了考虑了前$i - 1$组物品， 总体积为 $j - v_k$时的情况。

$f[i] [j]$ 表示考虑了前 $i$组物品，总体积为 $j$ 时的最大收益。

代码：

#include<bits/stdc++.h>
using namespace std;

int n, m, a[1001], v[1001], w[1001], f[1001][1001];
vector<int> c[1001];

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> a[i] >> v[i] >> w[i];
         c[a[i]].push_back(i);
    }
    for(int i = 1; i <= 1000; i++) {
        for(int j = 0; j <= m ; j++) {
            f[i][j] = f[i - 1][j];
            for(auto k : c[i]) {
                if(v[k] <= j)
                    f[i][j] = max(f[i][j], f[i - 1][j - v[k] ] + w[k]);
            }
        }
    }
    cout << f[1000][m] << endl;
}

优化代码

#include<bits/stdc++.h>
using namespace std;

int n, m, a[1001], v[1001], w[1001], f[1001];
vector<int> c[1001];

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> a[i] >> v[i] >> w[i];
         c[a[i]].push_back(i);
    }
    for(int i = 1; i <= 1000; i++) 
        for(int j = m; j ; j--) 
            for(auto k : c[i]) 
                if(v[k] <= j)
                    f[j] = max(f[j], f[j - v[k]] + w[k]);
    cout << f[m] << endl;
}

7.二维背包

题目描述

有 $n$ 种物品要放到一个袋子里，袋子的总容量为 $m$，我们一共有 $k$ 点体力值。第
$i$种物品的体积为 $vi$，把它放进袋子里会获得 $wi$ 的收益，并且消耗我们 $ti$ 点体力值，每种物品只能取一次。问如何选择物品，使得在物品的总体积不超过 $m$ 并且花费总体力不超过$k$ 的情况下，获得最大的收益？请求出最大收益。

数据范围：

$$1≤n,m,k,ai,vi,wi≤100$$

分析

相较于分组背包就是多了一个体力限制。

把考虑了前 $i$ 组物品以后，总体积为 $0~m$ ，总体力为 $0~k$ 时的最大收益都记下来。

考虑了前 $i$ 组物品， 总体积为 $j$，总体力为 $x$ 时分为两种情况：

Case 1： 第$i$ 组物品一个没取，问题就变成了考虑前 $i - 1$ 组物品，总体积为$j$ 时，总体力为$x$ 时的情况。

Case 2： 第$i$ 组物品取了， 我们枚举取了其中的物品$k$ ， 问题变成了考虑了前 $i - 1$ 组物品， 总体积为 $j - v_k$，总体力为$x - t_i$时的情况。

$f[i] [j] [x]$ 表示考虑了前$i$ 组物品，总体积为 $j$ ，总体力为$x$ 时的最大收益。

代码：

#include<bits/stdc++.h>
using namespace std;

int n, m, k, v[1001], w[1001], t[1001], f[101][101][101];

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

优化代码：

#include<bits/stdc++.h>
using namespace std;

int n, m, k, v[1001], w[1001], t[1001], f[101][101];

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

完结撒花~