知識點(diǎn)：sum就表示從 1+2+4+8+.....+ 2^(m-2)。   我們可以檢驗(yàn)， 在[1,Cn]中任意的數(shù) 我們都可以在這個序列中找到若干數(shù)相加得到。

第1行，2個整數(shù)，N和W中間用空格隔開。N為物品的種類，W為背包的容量。(1 <= N <= 100，1 <= W <= 50000)第2 - N + 1行，每行3個整數(shù)，Wi，Pi和Ci分別是物品體積、價值和數(shù)量。(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;}