题目概述

有 $n$ 个物品，每个物品的体积满足 $a\cdot 2^b$ ，背包体积为 $W$ ，求最大价值。

解题报告

直接上背包！因为每个物品体积满足 $a\cdot 2^b$ ，所以我们可以定义 $f[i][j]$ 表示倒着处理到第 $i$ 位，目前体积还剩下 $j$ 的方案数。然后每次先让 $f[i][2j+W_i]=f[i+1][j]$ ，之后做 $a=i$ 的物品的背包。

但是 $j$ 的范围要上天了啊，实际上只需要和 $2000$ 取个小的就行了，因为每次顶多用掉 $1000$ ，用掉乘个二又变回 $2000$ 了23333。

示例程序

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxv=2000,Log=30;

int n,V,f[Log+5][maxv+5],ans;
vector<int> w[Log+5],p[Log+5];

inline void Make(int ID,int x,int y){
    int b=0;while (!(x&1)) b++,x>>=1;
    w[b].push_back(x);p[b].push_back(y);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (scanf("%d%d",&n,&V);~n||~V;scanf("%d%d",&n,&V)){
        for (int i=0;i<=Log;i++) w[i].clear(),p[i].clear();
        for (int i=1,x,y;i<=n;i++) scanf("%d%d",&x,&y),Make(i,x,y);
        memset(f,192,sizeof(f));ans=f[0][0];f[Log+1][0]=0;
        for (int t=Log;~t;t--){
            for (int j=0,now=V>>t&1;j<=maxv;now<maxv-1?now+=2:now=maxv,j++)
                f[t][now]=max(f[t][now],f[t+1][j]);
            for (int i=0,si=w[t].size();i<si;i++)
                for (int j=0;j<=maxv-w[t][i];j++)
                    f[t][j]=max(f[t][j],f[t][j+w[t][i]]+p[t][i]);
        }
        for (int j=0;j<=maxv;j++) ans=max(ans,f[0][j]);printf("%d\n",ans);
    }
    return 0;
}