【题解】 bzoj1190: [HNOI2007]梦幻岛宝珠 （动态规划）

bzoj1190，懒得复制，戳我戳我

Solution:

• 这道题其实是一个背包（分组背包），但是由于数字比较大，就要重新构造dp式子。啃了三天才懂。
• (dp[i][j])表示背包容积为(j*2^i)时的最大价值。
• 首先，因为每一个物品一定是(a*2^b)，我们可以按照(b)值先按照普通的分组背包去做，处理出每个(b)值所对应的(dp)值
• 然后我们就是要把这些(dp)值累积起来，选择每组最大显然不合适，因为有可能每个组都剩下空间，剩余空间累加起来的空间还可以放物品，我们采用一下(dp)方法：

[dp[i][j] = max(dp[i][j] , dp[i][j-k]+dp[i-1][2*k+(w>>(i-1))]) ]

• (i)表示次方，(j)表示系数，(k)表示让出多少位置给(i-1)次方
• 我们次方从小（(1)）枚举到大（(W)最高位），系数从大枚举到小，要保证(i)位上的最大价值是没有更新过得，也就是不包括前面位置（(2^{i-1})）的物品，然后加上上一层（(i-1)）最大放的空间的(dp)值（因为空间最大，所以存的价值一定是最大的）
• 另外还有一个小细节，我们要把前面预处理每组背包时处理到(2)倍，因为后面更新时，会把(i)层腾的空间传给(i-1)层，例如(i)层腾了(k)空间，也就是(i-1)层多有(2*k)的空间，再加上(W)里面(i-1)位的空间就是(i-1)的空间最大
• 最后输出(dp[cnt][1])，(cnt)是最高位，因为是最高位，所以最高位上一定是(1)
• 看得还是比较迷糊的，戳这里，这个博客讲的挺详细的
• 好像(HNOI2007)的题目都好毒瘤23333……

---

Code:

//It is coded by Ning_Mew on 4.19
#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int maxn=107;

int n,cnt=0;
LL W,dp[maxn][2005],v,w;

int main(){
  while(1){
    memset(dp,0,sizeof(dp));
    scanf("%d%lld",&n,&W);
    if(n==-1)break;
    for(int i=1;i<=n;i++){
      scanf("%lld%lld",&w,&v);
      cnt=0;
      while(w%2==0)cnt++,w=w/2;
      //cout<<"w:"<<cnt<<' '<<w<<endl;
      for(int i=2000;i>=w;i--){
	dp[cnt][i]=max(dp[cnt][i],dp[cnt][i-w]+v);
      }
    }
    cnt=0;
    for(int i=30;i>=0;i--)if((W>>i)&1){cnt=i;break;}
    //cout<<"w:"<<cnt<<' '<<W<<endl;
    for(int i=1;i<=cnt;i++){
      for(int j=1000;j>=0;j--){
	for(int k=0;k<=j;k++){
	  dp[i][j]=max(dp[i][j],dp[i][j-k]+dp[i-1][2*k+((W>>(i-1))&1)]);
	}
      }
    }
    printf("%lld
",dp[cnt][1]);
  }
  return 0;
}