有 N种物品和一个容量是 V 的背包。第 i种物品最多有 si件，每件体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。
题干与多重背包问题Ⅰ相同，但数据范围不同

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i种物品的体积、价值和数量。

数据范围

0<N≤1000
0<V≤2000
0<vi,wi,si≤2000

二进制优化

  1. 将多重背包问题转换成01背包能够简化思考和代码的逻辑
  2. 任何一个实数都可以通过二进制数表示出来
  3. 多重背包问题核心就是每件物品取多少件可以获得最大价值
  4. 由于多重背包问题问的是最后的最优解所以之前是什么分组的并不重要所以可以用二进制规划数组
  5. 举现实例子说明这个优化的意思
    现在给出一堆苹果和10个箱子，选出n个苹果。将这一堆苹果分别按照1，2，4，8，16……512分到是个箱子里，那么由于任何一个数字x属于[0,1023]都可以从是个箱子里面的苹果数表示出来，这样选择的次数就是<=10次。
    如果要拿1001次苹果，传统就是要拿1001次；二进制的思维，就是拿7个箱子就行（分别是装有512，256，128，64，32，8，11个苹果的箱子一共七个，这样一来1001次操作优化为7次。
  6. 二进制优化，时间复杂度从O（n3）降低到O（n2logs）。

代码（二进制优化数量）

#include <iostream>
using namespace std;

const int N = 12010,M = 2010;   
//关于N为什么是12010 通过计算复杂度N*logS*V 2000 *log2000 * 1000
//二进制优化 把s变为logs

int n,m;
int v[N],w[N];
int f[M];

int main()
{
    cin >> n >> m;
    int cnt = 0;//分组的组别
    for(int i = 1;i <= n;i++)
    {
        int a,b,s;
        cin >> a >> b >> s;
        int k = 1;//（二进制的起点）
        while(k <= s)
        {
            cnt++;  //组别先增加
            v[cnt] = a * k; //存入k个物品的体积
            w[cnt] = b * k; //存入k个物品的价值
            s -= k; //物品个数减小k个
            k *= 2; //组别里个数指数增加（1，2，4，8，16……）
        }
        //k超过总数s  那么s-k会余出一部分，对于这一部分的处理
        if(s > 0)
        {
            cnt ++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }
    n = cnt; 
    //上方的for循环会把所有情况的值存在cnt个数组空间中，这个时候cnt各空间就是对应着需要计算的n
    //这样相当于将本来需要遍历的所有个数的情况 优化到 cnt个
    for(int i = 1;i <= n;i++)
    {
        //01背包的一维优化 从大到小   （可以看出 二进制优化后的多重背包其实就是个01背包问题了）
        for(int j = m;j >= v[i];j--)
        {
            f[j] = max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout << f[m] << endl;
    return 0;
}