今日复习01背包,完全背包,多重背包DP,以及多重背包优化

01背包

每个物品只能选一次，可以选或不选

f[i,j]表示选到前i个物品体积不超过j的最大价值

状态转移方程为f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i])

优化空间采用滚动数组,从大到小枚举体积即可

完全背包

每个物品可以选无限次，可以选或不选

f[i,j]同样表示选到前i个物品体积不超过j的最大价值

不过划分却为f[i-1][j]不选第i个和选第i个

状态转移方程f[ i , j ]=max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2*v]+ww,.........)

观察f[i,j-v]=max(f[i-1][j-v],f[i-1][j-2v]+w,f[i-1][j-3v]+2w.....)与上式子只差一个w

所以可以优化成

f[i][j]=max(f[i-1][j],f[i][j-v]+w),优化空间采用滚动数组，从小到大枚举体积即可

多重背包

每个物品可以选有限个，可以选或者不选

相对于完全背包，在取最大值时要多一重循环枚举每个物品选多少个

#include <iostream>
using namespace std;
int n,v;
const int N=110;
int V[N],W[N],S[N],f[N][N];int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>v;for(int i=1;i<=n;i++) cin>>V[i]>>W[i]>>S[i];for(int i=1;i<=n;i++)for(int j=1;j<=v;j++){for(int k=0;k<=S[i];k++)if(j>=V[i]*k)f[i][j]=max(f[i][j],f[i-1][j-k*V[i]]+W[i]*k);}cout<<f[n][v];return 0;
}

洛谷P1776 宝物筛选

朴素算法复杂度大概是O(n*v*si)

而数据给的是1e4*1e4*1e5

必然会超时

因此要采用二进制优化把多重背包转换为01背包

而可以将每个物品打包成二进制数的个数加一个差值例如34=1+2+4+8+16+3

因此可以转换为01背包问题从而进行优化

转换的个数根据结论大概是log(s)下取整+1

这边算出来大概是4e4,开个1e5保险

#include <iostream>
using namespace std;
const int N=1e5;//f[N][N]会爆内存,要优化空间
int v[N],w[N],f[N];int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n,m;cin>>n>>m;int cnt=0;//来记录新打包物品个数while(n--){int a,b,c;//价值,重量,个数cin>>a>>b>>c;int k=1;//第一个数while(k<=c){cnt++;v[cnt]=b*k;w[cnt]=a*k;c-=k;//减去他k<<=1;}if(c){cnt++;v[cnt]=c*b;w[cnt]=c*a;}}n=cnt;//更新新打包好的物品个数//接下来就是01背包了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];return 0;
}