[HNOI2007]梦幻岛宝珠

静静是他的， · 2020-10-30 21:18:30 · 题解

• 题意: 一个最大重量为2^{30}的 01背包，物品重量可以分解为a*2^{b}。

• 显然，暴力 01背包 是不可行的，只有10分。

• 就只能利用物品重量性质：

  1. 设 f_{i,j} 为 选了j*2^i 重量的最大价值， 实际上 2^i 以下的重量被忽略了。
  2. 考虑转移，同为 2^i 重量的物品间可以相互转移: 当前是第x个数： f_{i,j} = \max \{f_{i,j-w_x} + val_x\}

  就是一般的01背包。

  3. 不同 2^i 重量的物品的转移：

  考虑从 2^{i-1} 和 2^i 重量转移：

  f_{i,j} = \max\limits_{k=0}^{j} \{ f_{i-1,k\ast2 + [m \& (1 << b - 1)]} +f_{i,j-k}\}
  • f_{i-1,k\ast2 + [m \& (1 << b - 1)]}

  a. 从 j 拿出 k \ast 2^i 的重量个给 2^{i-1} 的，

  即 2\ast k \ast 2^{i-1} ， 得到：

  f_{i-1, 2\ast k}

  b. 最大价值 W 中，可能会多出一个 2^{i-1} ，

  例如: W = 2^{10} + 2^{9} ， 从 2^9 转移到 2^{10} 还能多选一个 2^9 即 [W \& 2^9] = 1

  也就是：

  f_{i - 1, 2 \ast k + [m \& (1 << b - 1) ]}
  • f_{i, j - k}

  拿出 k 后剩下 j - k 。

  4. 最后答案为 f_{len,1} ， 2^{len} 是最大小于W 的。

时间复杂度 O(T \ast len \ast 1000 \ast 1000) ， 常数略大。

加O2才过的垃圾代码：

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 2010;

int n, m;
long long w;
long long ai[MAXN], bi[MAXN], val[MAXN], f[32][1010];

int main(){
    while(cin >> n >> w){
        if (n == -1 && w == -1) break;
        memset(f, 0, sizeof(f));
        for(int i = 1; i <= n; i++){
            long long c;
            cin >> c >> val[i];
            ai[i] = (c / (c & (-c)));
            bi[i] = 0;
            for(c = (c & (-c)) >> 1; c; c >>= 1) bi[i]++;
        }

        for(int i = 1; i <= n; i++)
            for(int a = 1000; a >= ai[i]; a--)
                f[bi[i]][a] = max(f[bi[i]][a], f[bi[i]][a - ai[i]] + val[i]);   

        int len = 0;
        for(long long s = w>>1; s; s >>= 1) len++;

        long long  ans = 0;
        for(int b = 1; b <= len; b++){
            for(int a = 1000; a >= 0; a--)
                for(int k = 0; k <= a; k++){
                    f[b][a] = max(f[b][a], f[b][a - k] + f[b - 1][min(1000, (k << 1) | ( (w & (1 << (b - 1))) != 0))]);
                }
        }

        cout << f[len][1] << endl;

    }

    return 0;
}