当前位置：首页 > news >正文

背包问题概论（01背包，完全背包，多重背包）DP

news 来源：原创 2025/6/27 22:58:38

背包问题概论（01背包，完全背包，多重背包）DP

背包问题一种经典的组合优化问题，主要用于在有限的容量下选择物品以最大化总价值。它分为几种类型：
①：0/1背包问题：每种物品只能选择一次，目标是在不超过背包容量的情况下，选择物品使总价值最大化。
②：完全背包问题：每种物品可以选择多次，允许重复选择。
③：分数背包问题：物品可以分割，允许选择物品的一部分。
背包问题的解决方法通常包括动态规划（DP）和贪心算法等。

0-1背包完全背包【基础算法精讲 18】

01背包
01背包是一种动态规划问题，其核心在于状态转移方程。

对于以上这个01背包例题，很容易想出一个递归的写法

#include <bits/stdc++.h>
using namespace std;
#define N 1005
int w[N],c[N];
int dfs(int i,int m)
{if(i<0) return 0;if(m<c[i]) return dfs(i-1,m);return max(dfs(i-1,m),dfs(i-1,m-w[i])+c[i]);
}
int main()
{int m,n;cin>>m>>n;for(int i=0;i<n;i++) cin>>w[i]>>c[i];cout<<dfs(n-1,m);return 0;
}

dfs函数的第一个参数 i 代表物品索引，第二个参数 m 则代表背包容量，这个纯递归的思路当 n = 1000 时难以为继，所以可以采用记忆化的手法优化，类似的动态规划题均可思考使用记忆化去优化题解。

#include <bits/stdc++.h>
using namespace std;
#define N 1005
int w[N],c[N],f[N][N];
int main()
{int m,n;cin>>m>>n;for(int i=0;i<n;i++) cin>>w[i]>>c[i];for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){//  当前背包容量装不进第i个物品，则价值等于前i-1个物品if(j<w[i]) f[i][j]=f[i-1][j];// 能装，需进行决策是否选择第i个物品else f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+c[i]);}cout << f[n][m] << endl;return 0;
}

采用二维数组 f 来存储结果，f[i][j] 表示前 i 个物品，在容量为 j 时最大背包问题。显然这个题解把递归问题变成了递推问题，空间是否还能优化，01背包问题的模板为一维数组递推求解。

#include<bits/stdc++.h>
using namespace std;
#define N 1005
int w[N],c[N],f[N];
int main()
{int m,n;cin>>m>>n;for(int i=1;i<=n;i++)cin>>w[i]>>c[i];for(int i=1;i<=n;i++){for(int j=m;j>=w[i];j--)f[j]=max(f[j],f[j-w[i]]+c[i]);}cout<<f[m]<<endl;
}

本文仅给出代码，具体解答请读者观看视频进行理解。01背包不仅局限于此，还有诸多变式，感兴趣的可以稍后点击链接，移步大佬 “灵茶山艾府” 的推荐题单。leetcode灵茶山艾府dp题单

完全背包
完全背包与01背包相似，只是每个物品都可以选择无数次

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int f[N];
int v[N],w[N];
int main()
{int n,m;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]<<endl;
}

同样采用一位数组递推，但二者在内层循环有所不同，01背包为了避免物品重复选择导致结果出错，采用倒序递推（因为01背包后续点仅与前缀点原始数据有关，如果正序遍历会迭代掉原来的值，导致重复选择），完全背包则无此忧虑，因为每个物品都是无限的，反而需要考虑重复选择。
关于非背包问题却得出类似的状态转移方程，上面的灵神视频里总结的非常到位，大家不妨多看几次去理解。

多重背包
多重背包问题求解思路比较好想，我们把一个物品不同数量全部拆开，问题就变成01背包问题，只是有些物品价值和重量一样而已，对于01背包问题的求解没有影响。

#include<bits/stdc++.h>
using namespace std;const int N = 110;
int n, m, v[N], w[N], s[N], f[N][N];int main()
{cin >> n >> m;for (int i = 1; i <= n; i++)cin >> v[i] >> w[i] >> s[i];for (int i = 1; i <= n; ++i){for (int j = 0; j <= m; ++j){for (int k = 0; k <= s[i] && k * v[i] <= j; ++k){f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);  //k控制数量}}}cout << f[n][m] << endl;return 0;
}

显然上述问题对于数据量较大时任会超时，所以可以采用二进制优化问题。具体优化思路在于：每一个数字都可以用二进制进行唯一表示，所以把同样的物品数量这一数据的拆分方式由全部拆分改为二进制拆分。

#include<bits/stdc++.h>using namespace std;const int N = 25000, M = 2010;
//   1000*log2000
int n, m, v[N], w[N], f[N];int main()
{cin >> n >> m;int cnt = 0;for (int i = 1; i <= n; i++){int a, b, s; cin >> a >> b >> s;int k = 1;while (k <= s){cnt++;v[cnt] = a * k;w[cnt] = b * k;s -= k;k *= 2;}if (s > 0){cnt++;v[cnt] = a * s;w[cnt] = b * s;}}n = cnt;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;
}

背包问题概论（01背包，完全背包，多重背包）DP

相关文章：