题目链接：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1086

题解：怎么用二进制优化多重背包，举一个例子就明白了。

如果要放n个苹果，可以将n个苹果分成几个2的次方1，2，3，4，m^2然后n可以由这些按照某种组合来组合。

于是就知道怎么优化了。

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

const int M = 1e5 + 10;

int wi[110] , p[110] , c[110] , dp[M];

int main() {

    int n , w;

    scanf("%d%d" , &n , &w);

    for(int i = 1 ; i <= n ; i++) {

        scanf("%d%d%d" , &wi[i] , &p[i] , &c[i]);

    }

    memset(dp , 0 , sizeof(dp));

    for(int i = 1 ; i <= n ; i++) {

        int d1 = 1 , d2 = c[i];

        while(d1 < d2) {

            for(int j = w ; j >= d1 * wi[i] ; j--) {

                dp[j] = max(dp[j] , dp[j - d1 * wi[i]] + d1 * p[i]);

            }

            d2 -= d1;

            d1 *= 2;

        }

        for(int j = w ; j >= d2 * wi[i] ; j--) {

            dp[j] = max(dp[j] , dp[j - d2 * wi[i]] + d2 * p[i]);

        }

    }

    printf("%d\n" , dp[w]);

    return 0;

}