各式各样的DP:分层DP
/**************************************************************
Problem: 1190
User: lxy8584099
Language: C++
Result: Accepted
Time:100 ms
Memory:2580 kb
****************************************************************/
/*
分层DP
f i,j表示只用 a*(2^i)重量 总重量为j*(2^i) 的 答案
明显 a<=j
同一层 即 (2^i) 一层之间的转移就是普通的01背包
不同层转移
首先系数和w[i]加上上一层w[i-1]的一半
但是除法是强制取整的 所以加上(w[i-1]+1)>>1
然后枚举上层使用的系数(剩下的就是本层使用的)
进行max
a i,j表示第i层第j个物品重量的系数---a
b i,j表示第i层第j个物品的 价值
w i表示 第i层的物品系数总和
p i表示第i层物品个数
*/
#include<bits/stdc++.h>
using namespace std;
const int N=1050;
int n,m,mx,f[105][N],a[105][N],b[105][N],p[105],w[105];
int main()
{
while(scanf("%d%d",&n,&m))
{
memset(a,0,sizeof(a));memset(b,0,sizeof(b));
memset(p,0,sizeof(p));memset(w,0,sizeof(w));
memset(f,0,sizeof(f)); mx=0;
if(n==-1) break;
for(int i=1,x;i<=n;i++)
{
scanf("%d",&x);int k=0;
while(!(x&1)) k++,x>>=1;
a[k][++p[k]]=x; w[k]+=x;
mx=max(mx,k);scanf("%d",&b[k][p[k]]);
}
for(int i=0;i<=mx;i++) // 分层Dp
for(int j=1;j<=p[i];j++)
for(int k=w[i];k>=a[i][j];k--)
f[i][k]=max(f[i][k],f[i][k-a[i][j]]+b[i][j]);
while(m>>mx) mx++; mx--; // 找到实际能装下的最高层
for(int i=1;i<=mx;i++) // 合并
{
w[i]+=(w[i-1]+1)>>1;
for(int j=w[i];j>=0;j--)
for(int k=0;k<=j;k++) // 枚举上层使用
f[i][j]=max(f[i][j],
f[i][j-k]+f[i-1][min(w[i-1],(k<<1)|((m>>(i-1))&1))]);
// 上一层最多也不能超过 w[i-1] 或上 m的那一位是否为1
// 理由和 +(w[i-1]+1)>>1 相同
}
printf("%d\n",f[mx][1]);
}
return 0;
}
转载于:https://www.cnblogs.com/lxy8584099/p/10358686.html