有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<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=;
int read(){
int ans=,f=,c=getchar();
while(c<''||c>''){if(c=='-') f=-; c=getchar();}
while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}
return ans*f;
}
int n,m;
int c[M],w[M],h[M],f[];
int main()
{
n=read(); m=read();
for(int i=;i<=n;i++) c[i]=read(),w[i]=read(),h[i]=read();
for(int i=;i<=n;i++){
int now=h[i],j=;
while(j<now){
for(int k=m;k>=c[i]*j;k--) f[k]=max(f[k],f[k-c[i]*j]+w[i]*j);
now-=j; j*=;
}
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=;i<=m;i++) printf("[%d] ",f[i]);printf("\n");
} printf("%d\n",f[m]);
return ;
}