首页 > 代码库 > 背包模型
背包模型
01背包：从右往左（因为只能由上一个物品的状态退出，如果从左往右则前边的保存的已是装了这件物品的值）递推，放不放此物品
完全背包：从左往右递推
多重背包：二进制拆包，或用单调队列优化（应该不考吧看的不明白QAQ）
装满背包：只把f[0]设为0
分组背包：把有依赖关系的方程一组，然后在一个阶段了分别dp不取附件，取一个，取两个（只有主次依赖）
二维费用：再加一维费用的循环
混合背包模板
#include<iostream>#include<cstdio>#include<algorithm>#define maxn 205using namespace std;int n,m,w[maxn],v[maxn],a[maxn],dp[200005];int main(){ cin>>n>>m; int tw,tv,ta; for(int i = 1;i <= n;i++){ scanf("%d%d%d",&tw,&tv,&ta); if(tw > m) n--; else{ w[i] = tw; v[i] = tv; a[i] = ta; } } for(int i = 1;i <= n;i++){ if(a[i] == -1){ for(int j = w[i];j <= m;j++){ dp[j] = max(dp[j],dp[j-w[i]]+v[i]); } } if(a[i] == 1){ for(int j = m;j >= w[i];j--){ dp[j] = max(dp[j],dp[j-w[i]]+v[i]); } } if(a[i] > 1){ if(a[i] * w[i] >= m){ for(int j = w[i];j <= m;j++){ dp[j] = max(dp[j],dp[j-a[i]*w[i]]+a[i]*v[i]); } continue; } int k = 1; for(;k<a[i];){ for(int j = m;j >= w[i]*k;j--){ dp[j] = max(dp[j],dp[j-w[i]*k]+v[i]*k); } a[i] -= k; k = k<<1; } for(int j = m;j >= w[i]*a[i];j--){ dp[j] = max(dp[j],dp[j-w[i]*a[i]]+v[i]*a[i]); } } } cout<<dp[m]<<endl; return 0;}
优先队列优化
#include<iostream>#include<algorithm> int n,m,dp[200005],w[205],v[205],a[205];using namespace std;//“多重背包”通用模板const int MAX_V = 200005;//v、n、w：当前所处理的这类物品的体积、个数、价值//V：背包体积， MAX_V：背包的体积上限值//f[i]：体积为i的背包装前几种物品，能达到的价值上限。inline void pack(int f[], int V, int v, int n, int w){ if (n == 0 || v == 0) return; if (n == 1) { //01背包 for (int i = V; i >= v; --i) if (f[i] < f[i - v] + w) f[i] = f[i - v] + w; return; } if (n * v >= V - v + 1 || n == -1) { //完全背包(n >= V / v) for (int i = v; i <= V; ++i) if (f[i] < f[i - v] + w) f[i] = f[i - v] + w; return; } int va[MAX_V], vb[MAX_V]; //va/vb: 主/辅助队列 for (int j = 0; j < v; ++j) { //多重背包 int *pb = va, *pe = va - 1; //pb/pe分别指向队列首/末元素 int *qb = vb, *qe = vb - 1; //qb/qe分别指向辅助队列首/末元素 for (int k = j, i = 0; k <= V; k += v, ++i) { if (pe == pb + n) { //若队列大小达到指定值，第一个元素X出队。 if (*pb == *qb) ++qb; //若辅助队列第一个元素等于X，该元素也出队。 ++pb; } int tt = f[k] - i * w; *++pe = tt; //元素X进队 //删除辅助队列所有小于X的元素，qb到qe单调递减，也可以用二分法 while (qe >= qb && *qe < tt) --qe; *++qe = tt; //元素X也存放入辅助队列 f[k] = *qb + i * w; //辅助队列首元素恒为指定队列所有元素的最大值 } }}int main(){ cin>>n>>m; for(int i = 1;i <= n;i++){ cin>>w[i]>>v[i]>>a[i]; } for(int i = 1;i <= n;i++){ pack(dp,m,w[i],a[i],v[i]); } cout<<dp[m]; return 0;}
背包模型
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。