有N种物品，每种物品的数量为C1，C2......Cn。从中任选若干件放在容量为W的背包里，每种物品的体积为W1，W2......Wn（Wi为整数），与之相对应的价值为P1,P2......Pn（Pi为整数）。求背包能够容纳的最大价值。

 

Input

第1行，2个整数，N和W中间用空格隔开。N为物品的种类，W为背包的容量。(1 <= N <= 100，1 <= W <= 50000)第2 - N + 1行，每行3个整数，Wi，Pi和Ci分别是物品体积、价值和数量。(1 <= Wi, Pi <= 10000， 1 <= Ci <= 200)

Output

输出可以容纳的最大价值。

Input示例

3 6

 

2 2 5

3 3 8

1 4 1

Output示例

9

 

这就是裸的二进制优化dp

方法是：

将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。

使这些系数分别为 1,2,4,...,2^(k-1),n[i]-2^k+1，且k是满足n[i]-2^k+1>0的最大整数。

例如，如果n[i]为13，就将这种物品分成系数分别为1,2,4,6的四件物品。

这样就能在log的复杂度下求出所有搭配方法的答案辣

#include
         
          #include
          
           #include
           
            using namespace std;const int M=107;int read(){    int ans=0,f=1,c=getchar();    while(c<'0'||c>'9'){
       if(c=='-') f=-1; c=getchar();}    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}    return ans*f;}int n,m;int c[M],w[M],h[M],f[50007];int main(){    n=read(); m=read();    for(int i=1;i<=n;i++) c[i]=read(),w[i]=read(),h[i]=read();    for(int i=1;i<=n;i++){        int now=h[i],j=1;        while(j
            
             =c[i]*j;k--) f[k]=max(f[k],f[k-c[i]*j]+w[i]*j);            now-=j; j*=2;        }        for(int k=m;k>=c[i]*now;k--)                f[k]=max(f[k],f[k-c[i]*now]+w[i]*now);        for(int i=0;i<=m;i++) printf("[%d] ",f[i]);printf("\n");    }        printf("%d\n",f[m]);    return 0;}