开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 背包问题模型总结 -> 正文阅读

[数据结构与算法]背包问题模型总结

背包模型

遇到模型例题就总结进来！—— 持续更新中~

一、经典背包问题

1.01背包问题

01背包问题：每**个物品只能选一次**，要么选要么不选

每个物品：选，不选

思路：

在这里插入图片描述

（1）状态f[i][j]定义：前 i 个物品，背包容量 j 下的最优解（最大价值）：

当前的状态依赖于之前的状态，可以理解为从初始状态f[0][0] = 0开始决策，有 N 件物品，则需要 N 次决策，每一次对第 i 件物品的决策，状态f[i][j]不断由之前的状态更新而来。
（2）当前背包容量不够（j < v[i]），没得选，因此前 i 个物品最优解即为前 i?1个物品最优解：

对应代码：f[i][j] = f[i - 1][j]。
（3）当前背包容量够，可以选，因此需要决策选与不选第 i 个物品：

选：f[i][j] = f[i - 1][j - v[i]] + w[i]。
不选：f[i][j] = f[i - 1][j]。
我们的决策是如何取到最大价值，因此以上两种情况取max()。

时间复杂度：O(n * n)

【代码实现】二维版本：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;
int w[N], v[N];
int f[N][N];
int n, c;

// 容量不够：f[i][j] = f[i - 1][j]
// 容量还够：f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i] + v[i])

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

【代码实现】一维版本：

状态f[j]定义：N 件物品，背包容量j下的最优解。

//有优化版：观察状态转移方程f[i]只与上一层(i - 1)有关！

f[i] 仅用到了f[i-1]层,

j与j-v[i] 均小于j

若用到上一层的状态时,从大到小枚举, 反之从小到大哦

状态转移方程为：f[j - v[i]] + w[i] 。

注意枚举背包容量j必须从总体积开始（逆序枚举背包容量）。

逆序是为了保证更新当前状态时，用到的状态是上一轮的状态，保证每个物品只有一次或零次;

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;
int w[N], v[N];
int f[N];
int n, c;

int main()
{
    cin >> n >> c;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    
    for (int i = 1; i <= n; i ++ )
        for(int j = c; j >=  v[i]; j --)// 逆序枚举重量
        {
            
           f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    cout << f[c];        
    
    return 0;
}

2.完全背包问题

完全背包问题：每种物品可以取无限次，在背包容量一定的情况下求取最大价值。

每个物品：每个物品可以选0、1、2…个

思路：

在这里插入图片描述

（1）01背包：

二维：dp[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i])
一维：**f[j] = max(f[j], f[j - v[i]] + w[i])滚动优化：从背包容量c，循环降序**到当前物品重量v[i]

（2）完全背包：

三维：dp[i][j] = max(f[i - 1][j], f[i - 1][j - k * v[i]] + k * w[i])，三维非常容易就炸了
二维：由上述三维变形得：f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i])，（注意与01的二分及其相似但又存在区别）
一维：**f[j] = max(f[j], f[j - v[i]] + w[i])滚动优化：从当前物品重量w[i]，循环正序**升到背包容量c

【代码实现】二维版本：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;


const int N = 1010;
int v[N], w[N];
int f[N][N];
int n, c;


int main()
{
    cin >> n >> c;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    
    for (int i = 1; i <= n; i ++ )
        for(int j = 0; j <= c; 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][c];    
    
    return 0;
}

【代码实现】一维版本：

注意：顺序枚举体积

在这里，因为每个物品可以取任意多次，所以不再强求用上一轮的状态，即本轮放过的物品，在后面还可以再放;

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;


const int N = 1010;
int v[N], w[N];
int f[N];
int n, c;


int main()
{
    cin >> n >> c;
    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 <= c; j ++)// 顺序枚举背包容量
        {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    cout << f[c];    
    
    return 0;
}

【记忆】

所有背包问题，当空间优化成一维后，只有完全背包问题的体积是从小到达循环的！

不优化空间的话，无所谓，一般以这样的顺序

	for 物品
		for 体积
			for 决策

3.多重背包问题

多重背包问题：每种物品有si件（有限次数）

每个物品：每个物品可以选0、1、2…si个（上限为si个）

多重背包I

思路：将多重背包转化为01背包

将si件物品都存起来，转换为有si个物品，每个物品有一件

时间复杂度：O(n * v * s)~O(n^3)

【代码实现】

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;
int v[N], w[N];
int f[N];
int cnt;
int n, c;


int main()
{
    cin >> n >> c;
    
    for (int i = 1; i <= n; i ++ )
    {
        int vi, wi, si;
        cin >> vi >> wi >> si;
        
        for (int j = 1; j <= si; j ++ )
        {
            cnt ++;
            v[cnt] = vi;
            w[cnt] = wi;
        }
    }
    
    // 01背包
    for (int i = 1; i <= cnt; i ++ )// 这里是cnt
        for (int j = c; j >= v[i]; j -- )
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    
    cout << f[c];        
    
    
    return 0;
}

多重背包II

二进制优化：

时间复杂度：O(n*v*log(s)) ~ O(nlongn)

【代码实现】

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;
int v[N], w[N];
int f[N];
int cnt;
int n, c;


int main()
{
    cin >> n >> c;
    
    for (int i = 1; i <= n; i ++ )
    {
        int vi, wi, si;
        cin >> vi >> wi >> si;
        
		// 对si进行二进制化 比如有10件一样的物品 
		// 我们转换为4组不同物品 1 2 4 3
		// 这4组物品对应的体积分别为：1*v1 2*v2 4*v3 3*v4 
        
        int t = 1; // 进位
        while(t <= si)
        {
            cnt ++;
            v[cnt] = vi * t;
            w[cnt] = wi * t;
            si -= t;
            t *= 2;
            
        }
        if(si > 0)
        {
            cnt ++;
            v[cnt] = vi * si;
            w[cnt] = wi * si;
        }
    }
    
    // 01背包
    for (int i = 1; i <= cnt; i ++ )// 这里是cnt
        for (int j = c; j >= v[i]; j -- )
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    
    cout << f[c];        
    
    
    return 0;
}

多重背包III

待补

在这里插入图片描述

4.分组背包问题

分组背包问题：有n组物品，每组物品里边有若干个物品，同样一组物品里边最多选择一个物品！

思路：

在这里插入图片描述

【代码实现】

一维优化：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;
int v[N][N], w[N][N];
int f[N];
int s[N];
int n, c;

int main()
{
    cin >> n >> c;
    
    for (int i = 1; i <= n; i ++ )
    {
        cin >> s[i];
        for(int j = 0; j < s[i]; j ++) 
            cin >> v[i][j] >> w[i][j];
    }
    // 类似01背包的优化处理
    for(int i = 1; i <= n; i ++)
        for(int j = c; j >= 0; j --)
            for(int k = 0; k < s[i]; k ++)
            if(v[i][k] <= j)
                f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
    cout << f[c];            
    return 0;
}

5.混合背包问题

二、巩固练习

01背包经典问题

1.采药

【题目链接】423. 采药 - AcWing题库

思路：经典01背包问题

我们把 m 个单位时间看做是 背包的容量

每株草药看做是物品，草药采集所需时间看做是 物品的体积，草药的价值看做是 物品的价值

那么本题就可以看做是一个背包问题了

由于每株草药只有一个，也就是要么采，要么不采两种方案，所以该题是一个 01背包模型

在规定的时间内如何时采药价值最大。

【代码实现】

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;
int f[N];
int n, m;

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

2. 装箱问题

【题目链接】1024. 装箱问题 - AcWing题库

思路：经典01背包问题

要是空间尽可能小，那么装的就要尽可能多。

最终答案为：m - f[m]

【代码实现】

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;
int f[N];
int n, c;

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

3.数字组合（01背包方案数）

思路：

对于本题我们可以把每个 正整数 看作是一个物品

正整数的值就是物品的体积

我们方案选择的目标是最终 体积恰好为 m 时的 方案数

于是本题就变成了 01背包求解方案数的问题了

目标状态：f[n][m]

初始化f[i][0] = 1，即f[0] = 1;

在这里插入图片描述

【代码实现】

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;
int f[N];
int n, m;

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

4.开心的金明

在这里插入图片描述

思路：01背包模型

妈妈给今明的钱：背包的容量

物品的价格：物品的体积

物品的价格与等级的乘积（w[i] * 等级）：物品的价值

这样就可以转为经典01背包模型了

状态表示：f[i][j]

【代码实现】

二维空间不够，30000就爆了

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 20000;
int f[N][N];
int w[N], v[N];
int n, m;

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

一维优化：

【代码实现】

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 30010;
int f[N];
int w[N], v[N];
int n, m;

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

完全背包问题

1.买书（完全背包方案数）

【题目链接】1023. 买书 - AcWing题库

一共有n个物品，每个物品有体积vi，价值wi，每个物品能够选多次

求总体积不超过m的方案数

这是一道裸的完全背包问题求解方案数
在这里插入图片描述

初始化：f[0][0] = 1，即一维：f[0] = 1。

【代码实现】

二维版本：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;
int v[5] = {0, 10, 20, 50, 100};
int f[N][N];


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

【代码实现】

一维版本：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;
int v[5] = {0, 10, 20, 50, 100};
int f[N];


 
int main()
{
    int m;
    cin >> m;
    
    f[0] = 1;
    for (int i = 1; i <= 4; i ++ )
        for (int j = v[i]; j <= m; j ++ )// 顺序枚举
            f[j] += f[j - v[i]];
          
    cout << f[m];
    return 0;
}

多重背包问题

1. 庆功会

【题目链接】1019. 庆功会 - AcWing题库

每件物品有有限个，可以取0~si个，经典多重背包问题，而这题就是一道裸题。

【代码实现】

朴素方法实现：

时间复杂度：n * v * s = 6000 * 1000 * 10 ~1e7，没有爆炸，因此多重背包的三种实现方式都可以适用！

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;
int v[N], w[N];
int f[N];
int cnt;

int main()
{
    int n, m;
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++ )
    {
        int vi, wi, si;
        cin >> vi >> wi >> si;
        
        for(int i = 1; i <= si; i ++)
        {
            cnt ++;
            v[cnt] = vi;
            w[cnt] = wi;
        }
    }
    
    //01背包
    for (int i = 1; i <= cnt; i ++ )// 注意：这里时 cnt
        for(int j = m; j >= v[i]; j --)// 逆序
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    
    cout << f[m];        
    
    return 0;
}

二维费用的背包问题

1.二维费用的背包问题

【题目链接】8. 二维费用的背包问题 - AcWing题库

有 n件物品和一个容量为 V 的背包，背包最大承重是 M
每件物品只能用一次，第 i件物品的体积是 vi，重量是 mi，价值是 wi
求解一个选物品的方案，使得总体积不超过 V，总重量不超过 M 的，且总价值最大

分析

二维费用01背包问题

每件物品只能用一次因此是个 01背包模型

费用一共有两个，一个是体积，一个是重量，因此是个 01背包二维费用问题

思路：

在这里插入图片描述

【代码实现】

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;
int f[N][N];
int n, V, M;

int main()
{
    cin >> n >> V >> M;
    
    for (int i = 1; i <= n; i ++ )
    {
        int vi, mi, wi;
        cin >> vi >> mi >> wi;
        for (int j = V; j >= vi; j -- )// 逆序
            for (int k = M; k >= mi; k -- )// 逆序
                f[j][k] = max(f[j][k], f[j - vi][k - mi] + wi);
    }
    
    cout << f[V][M];
    
    return 0;
}

2.宠物小精灵之收服

【题目链接】1022. 宠物小精灵之收服 - AcWing题库

思路：

二维费用01背包问题

花费1：精灵球数量

花费2：皮卡丘体力值

价值：小精灵的数量(每只精灵价值为1)

状态表示：f[i,j,k]表示所有只考虑前i个物品，且花费1不超过j，花费2不超过k的选法的最大值

状态计算：f[i,j,k] = Max(f[i - 1,j,k],f[i - 1,j - v1[i],k - v2[i]] + 1)

注意：题目说道：使得皮卡丘体力小于等于0的野生小精灵也不会被小智收服，因此皮卡丘的体力值需在V2 - 1时开始

【代码实现】

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;
int f[N][N];



int main()
{
    int V1, V2, n;
    cin >> V1 >> V2 >> n;
    for (int i = 1; i <= n; i ++ )
    {
        int v1, v2;
        cin >> v1 >> v2;
        for (int j = V1; j >= v1; j -- )
            for (int k = V2 - 1; k >= v2; k -- )
                f[j][k] = max(f[j][k], f[j - v1][k - v2] + 1);
    }
    cout << f[V1][V2 - 1] << ' ';
    
    //找到满足最大价值的所有状态里，第二维费用消耗最少的
    int min_cost = V2;
    for(int k = 0; k <= V2 - 1; k ++)
    {
        if(f[V1][k] == f[V1][V2 - 1])
            min_cost = min(min_cost, k);
    }
    cout <<V2 - min_cost;
    return 0;
}

3.潜水员

【题目链接】1020. 潜水员 - AcWing题库

在这里插入图片描述

注意：即使所需要的氧气或者氮气所需的是数量是负数，但其所需数量与0是等价的，因此可以通过所需数量为0来转移

【代码实现】

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 25, M = 80;
int f[N][M];
int m, n, k;

int main()
{
    cin >> n >> m >> k;
    
    // 求最大值：初始化
    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;
    
    while(k --)
    {
        int v1, v2, w;
        cin >> v1 >> v2 >> w;
        
        for(int i = n; i >= 0; i --)
            for(int j = m; j >= 0; j --)
                f[i][j] = min(f[i][j], f[max(0, i - v1)][max(0, j - v2)] + w);
    }
    
    cout << f[n][m];    
    return 0;
}