给你N颗宝石，每颗宝石都有重量和价值。要你从这些宝石中选取一些宝石，保证总重量不超过W，且总价值最大为，并输出最大的总价值。数据范围：N<=100;W<=2^30,并且保证每颗宝石的重量符合a*2^b（a<=10;b<=30）
题解：
显然这是一个01背包，但是体积容积都特别大。
事实上，每颗宝石体积在2进制情况下的有效位数都特别有限，可以对体积按位dp。
F[i,j]表示当前DP到第i位，使用j*2^(i-1)体积可以得到的最大价值。对于i的阶段，只要用b=i-1的宝石去DP，然后进位转移到下一阶段。
因为a<=10，n<=100，j最多为1000。
注意考虑上界，需额外开一个数组表示所考虑有效位数之后的数都在W对应范围内的情况。
代码：
uses math; var i,j,k,l,n,m,ii,ww:longint; tot,w:int64; a:array[0..1,0..40,0..1001]of int64; s:array[0..40]of longint; b:array[0..101,0..2]of int64; t:array[0..2]of int64; begin while true do begin readln(n,w); tot:=0; //w:=50000; if n=-1 then break; for i:=1 to n do begin readln(b[i,1],b[i,0]); b[i,2]:=1; while b[i,1] mod 2=0 do begin b[i,1]:=b[i,1] div 2; inc(b[i,2]); end; end; for i:=1 to n-1 do for j:=i+1 to n do if b[i,2]>b[j,2] then begin t:=b[i]; b[i]:=b[j]; b[j]:=t; end; fillchar(a,sizeof(a),0); if n=-1 then break; l:=0; while w>0 do begin inc(l); s[l]:=w mod 2; w:=w div 2; end; ii:=1; for i:=1 to l do begin for j:=0 to 1000 do if(s[i-1]=1)or(j mod 2=0)then begin a[0,i,j div 2]:=max(a[0,i,j div 2],a[0,i-1,j]); a[0,i,j div 2]:=max(a[1,i,j div 2],a[0,i-1,j]); end; for j:=0 to 1000 do begin a[1,i,(j div 2)+1]:=max(a[1,i,(j div 2)+1],a[1,i-1,j]); if j mod 2=0 then a[1,i,j div 2]:=max(a[1,i,j div 2],a[1,i-1,j]); end; while(ii<=n)and(b[ii,2]<=i)do begin for j:=1000-b[ii,1] downto 0 do begin a[0,i,j+b[ii,1]]:=max(a[0,i,j+b[ii,1]],a[0,i,j]+b[ii,0]); a[1,i,j+b[ii,1]]:=max(a[1,i,j+b[ii,1]],a[1,i,j]+b[ii,0]); end; inc(ii); end; for j:=1 to 1000 do begin a[0,i,j]:=max(a[0,i,j],a[0,i,j-1]); a[1,i,j]:=max(a[1,i,j-1],a[1,i,j]); end; end; writeln(max(a[1,l,1],a[0,l,1])); end; end.
原文：http://www.cnblogs.com/GhostReach/p/6254898.html