知识点：sum就表示从 1+2+4+8+.....+ 2^(m-2)。   我们可以检验， 在[1,Cn]中任意的数 我们都可以在这个序列中找到若干数相加得到。

第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 62 2 53 3 81 4 1Output示例
9
#include<cstdio>#include<iostream>using namespace std;int main(){	int n,w,dp[50002]={0},wt,p,c;	scanf("%d%d",&n,&w);	while(n--){		scanf("%d%d%d",&wt,&p,&c);		for(int k=1;k<=c;c-=k,k<<=1){			for(int j=w;j>=wt*k;j--)			dp[j]=max(dp[j],dp[j-wt*k]+p*k);		}		if(c)		for(int j=w;j>=wt*c;j--)			dp[j]=max(dp[j],dp[j-wt*c]+p*c);	}	PRintf("%d/n",dp[w]);	return 0;}