這題是在01背包問題的基礎上，擴充了重量，需要用時間換空間。
思路：
1.仔細看題，注意到重量wi為a*2^b（a<=10，b<=30），很容易想到要按 b 分開做背包的DP。接下來的重點就是怎麼使DP從b-1繼承到b。
2.再仔細看題，發現只有一次詢問，那麼就可以在這個W上做文章——依W的大小進行所有的DP。由於是按b的大小進行DP，所以把數都看成二進制位來繼承和轉移，每對一組 b 相同的數做完後，就略去這一二進制位。
實現：
1.“去位”：若W的二進制數上第 i 位為1，那麼這時背包裡已經放的物品的重量的第 i 位為0或1都無所謂，裝得了；若W的二進制數上第 i 位為0，那麼背包已有的重量的第 i 位為1就要從二進制的前一位借一個“1”拿來用。
2.對每組 b 進行DP時，直接用最大的背包容量N*wi（mW），之後轉移時再按W進行修改就行了。
其中，以上實現可行的原因是：
對於每個第 i 位，它處於一個很“尴尬”的境地，它的前一位一給就是給“1”，對於它就是“2”了，多了也無需退回去。因為對於每個第 j 位，它的下一位根本就幫不了它，貢獻“1”對於它也只是“0.5”，是沒有用的。因此要略去某一位時，只需干脆地按W是否能滿足它這一位的需求來對自己的前一位進行調整。
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 #include<algorithm>
6 using namespace std;
7
8 typedef long long LL;
9 const int N=110,M=30,mW=1000;
10 int n,W;
11 struct node{int w,v,a,b;}s[N];
12 LL f[M+10][mW+10];
13
14 bool cmp(node x,node y)
15 { return x.b<y.b; }
16 LL mmax(LL x,LL y)
17 { return x>y?x:y; }
18
19 int main()
20 {
21 while (1)
22 {
23 scanf("%d%d",&n,&W);
24 if (n==-1&&W==-1) break;
25 for (int i=1;i<=n;i++)
26 {
27 scanf("%d%d",&s[i].w,&s[i].v);
28 s[i].a=s[i].w,s[i].b=0;
29 while (s[i].a%2==0) s[i].a/=2,s[i].b++;
30 }
31 sort(s+1,s+1+n,cmp);
32 int l,r;
33 l=1;
34 memset(f,0,sizeof(f));
35 for (int i=0;i<=M;i++)
36 {
37 r=l-1;//
38 while (r<n && s[r+1].b==i) r++;//<n
39 for (int j=l;j<=r;j++)
40 for (int k=mW;k>=s[j].a;k--)
41 f[i][k]=mmax(f[i][k],f[i][k-s[j].a]+s[j].v);
42 for (int j=0;j<=mW;j++)//or (int j=mW;j>=0;j--)
43 if (W&(1<<i)) f[i+1][j>>1]=mmax(f[i+1][j>>1],f[i][j]);
44 else f[i+1][(j+1)>>1]=mmax(f[i+1][(j+1)>>1],f[i][j]);
45 l=r+1;
46 }
47 printf("%lld\n",f[31][0]);
48 }
49 return 0;
50 }
