luogu link
写于 2023.08.20
01 背包
朴素算法
//01背包模型
//给出m个物品及其价值，求在空间为T的背包中可以装的最大价值
#include<bits/stdc++.h>
using namespace std;
int ans[101][1001];//a[i][q]表示空间为q,在1~i个物品中取物品的最大价值
int w[101],c[101];
int main(){int m,n;scanf("%d %d",&m,&n);for(int i=1;i<=n;i++) scanf("%d %d",&w[i],&c[i]);for(int i=1;i<=n;i++){//枚举每个物品 for(int q=0;q<=m;q++){//枚举剩余空间 if(q<w[i]) ans[i][q]=ans[i-1][q];//不够放物品i了,不放 else ans[i][q]=max(ans[i-1][q],ans[i-1][q-w[i]]+c[i]);//放和不放物品i间取最大值 }}printf("%d",ans[n][m]);//ans[n][m]即为答案 return 0;
}
降维
#include<bits/stdc++.h>
using namespace std;
int ans[1001];
int w[101],c[101];
int main(){int m,n;scanf("%d %d",&m,&n);for(int i=1;i<=n;i++) scanf("%d %d",&w[i],&c[i]);for(int i=1;i<=n;i++){for(int q=m;q>=w[i];q--){//从后往前保证答案正确,注意当当前空间已经放不下(小于w[i])时就不用再考虑了 ans[q]=max(ans[q],ans[q-w[i]]+c[i]);//放和不放物品i间取最大值 }}printf("%d",ans[m]);//ans[m]即为答案 return 0;
}
完全背包
朴素
//完全背包模型 与01背包相比,每一种物品均可以取无限次
#include<bits/stdc++.h>
using namespace std;
int w[10005],v[10005];
long long f[10001][10001];
int main(){int m,n;scanf("%d %d",&m,&n);for(int i=1;i<=n;i++) scanf("%d %d",&w[i],&v[i]);for(int i=1;i<=n;i++){for(int q=0;q<=m;q++){//这里的i,q含义与上面的01背包相同 /*容易想到用循环枚举每种物品出现的次数，如下 for(int k=0;k*w[i]<=q;k++){//第i种物品取k个 f[i][q]=max(f[i-1][q],f[i-1][j-k*w[i]]+k*v[i]);}但可以发现这个循环可以直接被优化掉 注意到f[i][q-w[i]]为当前情况少取1个的最优解这样问题就又变为了取或不取,与01背包思路相同 */ f[i][q]=max(f[i-1][q],f[i][q-w[i]]+v[i]); }}printf("%lld",f[n][m]);return 0;
}
降维
//完全背包
#include<bits/stdc++.h>
using namespace std;
int w[10005],v[10005];
long long f[10000001];
int main(){int m,n;scanf("%d %d",&m,&n);for(int i=1;i<=n;i++) scanf("%d %d",&w[i],&v[i]);for(int i=1;i<=n;i++){for(int q=w[i];q<=m;q++){f[q]=max(f[q],f[q-w[i]]+v[i]); }}printf("%lld",f[m]);return 0;
}
分组背包
#include<bits/stdc++.h>
using namespace std;
int f[1005];//意义与先前已经给出的模型相同
bool group[1005];//辅助数组,标记组数
vector<int> w[1005],v[1005];//w[i],v[i]表示第i组的占用的空间及价值
int main(){int m,n,temw,temv,c;scanf("%d %d",&m,&n);for(int i=1;i<=n;i++){scanf("%d %d %d",&temw,&temv,&c);w[c].push_back(temw);//为第c组添加数据 v[c].push_back(temv);group[c]=true;//标记 }int n1=0;for(int i=1;i<=n;i++) if(group[i]) n1++;//n1为出现的组数 for(int i=1;i<=n1;i++){//第i组 for(int q=m;q>=0;q--){//背包剩余容量,此处直接给出一维优化,注意由于重量不确定,需要枚举到0 for(int j=0;j<w[i].size();j++){//本组的每一个元素 //取或不取的最大值 if(q>=w[i][j]) f[q]=max(f[q],f[q-w[i][j]]+v[i][j]); }//这样做每一组只会取一个}}printf("%d",f[m]);return 0;
}
LXS (最长 XX 子序列)
//求最长不升/不降/升/降子序列长度模型,此处以最长不升子序列为例
//注意,本程序并不能求出最长不升/不降/升/降子序列,仅能求出它们的长度
#include<bits/stdc++.h>
using namespace std;
vector<int> a;//a[i]表示长度为i+1的最长不升/不降子序列的最后一项
int num[100005];
bool cmp(const int &a,const int &b){return a>b;
}
int main(){int n;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&num[i]);for(int i=1;i<=n;i++){if(a.empty()||num[i]<=a[a.size()-1]){/*不降：num[i]>=a[a.size()-1]上升：num[i]>a[a.size()-1]下降：num[i]<a[a.size()-1]此处表示当前需要放置的数字可以直接添加至已有序列的末尾,故直接添加 */a.push_back(num[i]);continue;}int k=upper_bound(a.begin(),a.end(),num[i],cmp)-a.begin();/*不降：upper_bound(a.begin(),a.end(),num[i]);上升：lower_bound(a.begin(),a.end(),num[i]);下降：lower_bound(a.begin(),a.end(),num[i],cmp);注意到我们维护的序列必定有序，所以可以使用二分查找找到第一个大于/小于/大于等于/小于等于当前数的位置,并用当前数替换它这是因为当前数小于等于/大于等于/小于/大于找到的数,对后续数字的添加更为有利 */ a[k]=num[i];}printf("%d",a.size());//求解完整个数列后a的长度就是最长不升/不降/升/降子序列的长度return 0;
}
多重背包
朴素
#include<bits/stdc++.h>
using namespace std;
struct node{int v,w,m;
} a[105];
int ans[40005];
int main(){int n,t;scanf("%d %d",&n,&t);for(int i=1;i<=n;i++) scanf("%d %d %d",&a[i].v,&a[i].w,&a[i].m);for(int i=1;i<=n;i++){for(int q=t;q>=0;q--){for(int j=1;j<=a[i].m&&j*a[i].w<=q;j++){ans[q]=max(ans[q],ans[q-j*a[i].w]+j*a[i].v);}}}printf("%d",ans[t]);return 0;
}
二进制优化
//多重背包
#include<bits/stdc++.h>
using namespace std;
struct node{int v,w;void Set(int V,int W){v=V,w=W;}
} a[100005];
int nown;
int ans[40005];
void work(int v,int w,int m){//对输入的v,w,m进行二进制拆分//二进制拆分的原理：如果x=2^0+2^1+...+2^k+p,//则0~x的所有数均可以使用2^0,2^1,...,2^k,p之间的组合(取或不取)表示 int cnt=1;while(m-cnt>0){a[++nown].Set(v*cnt,w*cnt);m-=cnt,cnt<<=1;//cnt的值依次为：2^0,2^1,2^2,... }a[++nown].Set(v*m,w*m);//最后m的值即为最终剩下的数(p)
}
int main(){int n,t,v,w,m;scanf("%d %d",&n,&t);for(int i=1;i<=n;i++){scanf("%d %d %d",&v,&w,&m);work(v,w,m);//拆包后问题转换为普通的01背包问题 }for(int i=1;i<=nown;i++){for(int q=t;q>=a[i].w;q--){ans[q]=max(ans[q],ans[q-a[i].w]+a[i].v);}}printf("%d",ans[t]);return 0;
}
单调队列
#include<bits/stdc++.h>
using namespace std;
struct FSI{template<typename T>FSI& operator >>(T&res){res=0; T f=1; char ch=getchar();while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)){res=(res*10)+(ch-48);ch=getchar();}res*=f;return *this;}
} scan;
typedef long long ll;
const int N=105,M=4e4+5;
int v[N],w[N],cnt[N];
ll dp[2][M];
int q[M],head,tail;
int main(){int n,m;scan>>n>>m;for(int i=1;i<=n;i++) scan>>v[i]>>w[i]>>cnt[i];
// 多重背包: f[i][j]=max(f[i-1][j-k*w[i]]+k*v[i]), k<=cnt[i]
// 记 g[x][y]=f[i][y+x*w[i]],h[x][y]=f[i-1][y+x*w[i]].(0<=y<w[i], 事实上背包中很可能并没有 x 个 i 物品, 只是我们为方便 i 物品的转移假定的)
// 即 g[x][y]=max(h[x-k][y]+k*v[i])=max(h[x-k][y]-(x-k)*v[i])+x*v[i], 可以枚举 y 之后单调队列优化.memset(dp[0],0xcf,sizeof(dp[0]));dp[0][0]=0;for(int i=1;i<=n;i++){for(int y=0;y<w[i];y++){head=1,tail=0;q[++tail]=0;#define f(x) (dp[(i-1)&1][(x)*w[i]+y]-1ll*(x)*v[i])for(int x=0;x*w[i]+y<=m;x++){while(head<=tail&&q[head]<x-cnt[i]) head++;while(head<=tail&&f(q[tail])<=f(x)) tail--;q[++tail]=x;dp[i&1][x*w[i]+y]=f(q[head])+1ll*x*v[i];}}}ll res=0;for(int j=0;j<=m;j++) res=max(res,dp[n&1][j]);printf("%lld\n",res);return 0;
}
事实上对多重背包的单调队列优化是基于完全背包的，你会发现如果物品个数足够多，单调队列的队头永远不会弹掉，变为完全背包。