题目链接：
问题描述：
有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
多重背包问题，一开始其实是这样想的：
正常来讲，多重背包就是把一个物品很多件，看成多个相同物品，
中间加一重循环，像这样：但是！但是！
for(int i = 1; i <=n; i++)
for(int k = 1; k <= c[i]; k++)
for(int j = W; j >= w[i]*k; j--)
dp[j] = max(dp[j], dp[j-w[i] * k] + p[i] * k);但是这样其实是错的，会多放。鄙人愚钝，一开始根本不明白。
二进制思想：
任何整数都可以表示为多个二进制数相加。
假如说现在某种物品有三件，那么dp的时候，要算三次，分别为：放一件的时候，放两件的时候，放三件的时候，，，要三次循环，何不知，在放两件的时候，可能出现第一件已经放入的情况了，这时候其实是放了三件，等到三个一起放的时候，可能出现已经放过一件或两件或三件了。。所以一定要用二进制方法
定理：一个正整数n可以被分解成1,2,4,…,2^(k-1),n-2^k+1（k是满足n-2^k+1>0的最大整数）的形式，且1～n之内的所有整数均可以唯一表示成1,2,4,…,2^(k-1),n-2^k+1中某几个数的和的形式。
证明如下：
（1） 数列1,2,4,…,2^(k-1),n-2^k+1中所有元素的和为n，所以若干元素的和的范围为：[1, n]；
（2）如果正整数t<= 2^k – 1,则t一定能用1,2,4,…,2^(k-1)中某几个数的和表示，这个很容易证明：我们把t的二进制表示写出来，很明显，t可以表示成n=a0*2^0+a1*2^1+…+ak*2^（k-1），其中ak=0或者1，表示t的第ak位二进制数为0或者1.
（3）如果t>=2^k,设s=n-2^k+1，则t-s<=2^k-1，因而t-s可以表示成1,2,4,…,2^(k-1)中某几个数的和的形式，进而t可以表示成1,2,4,…,2^(k-1)，s中某几个数的和（加数中一定含有s）的形式。
完整代码如下：
/**************************************************************
> File Name: 1085_second.cpp
> Author: dulun
> Mail: dulun@xiyoulinux.org
> Created Time: 2016年03月18日 星期五 13时20分34秒
******************************************************/
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define LL long long
using namespace std;
const int N = 50086;
int dp[N];
int main()
{
int n, W;
scanf("%d%d", &n, &W);
int maxx = 0;
for(int i = 1; i <= n; i++)
{
int w, p, c;
cin>>w>>p>>c;
for(int k = 1; k <= c; c-=k, k<<=1)
for(int j = W; j >= w*k; j--)
{
dp[j] = max(dp[j], dp[j-w*k]+p*k);
}
if(C == 0) continue;
for(int j = W; j>= w*c; j--) dp[j] = max(dp[j], dp[j-w*c]+c*p);
}
cout<<dp[W]<<endl;
return 0;
}