算法——动态规划

多重背包2问题其实跟多重背包一的大致思路一样，都是采用将多重背包转化成01背包的思路进行求解。
而我们不难可以发现，多重背包问题2的数据范围比普通的多重背包问题1的数据范围要大。
在这里，我们采用相应的措施就是使用二进制优化。
众所周知，我们的电脑采用的都是二进制的思路，由于每个环节都有是与否两种选择，因此，只要数位足够大，就可以表示我们平时的数字。
其实，二进制的每位都为前一位的2倍（在十进制下），按此方法便可以表示我们的数。
例如：1=1;2=2;3=1+2;4=4;5=1+4;6=2+4;7=1+2+4;8=8;9=1+8......
01背包参考链接

C++ 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+100;
ll v[N],w[N];
ll f[N];
int main()
{
    ll n,m;
    ll cnt=1;
    cin>>n>>m;
    ll a,b,c;
    for(ll i=1;i<=n;i++)
    {
        cin>>a>>b>>c;
        ll k=1;
        while(k<=c)
        {
            v[cnt]=a*k;
            w[cnt]=b*k;
            c-=k;
            k*=2;
            cnt++;
        }//采用二进制优化
        if(c!=0)
        {
            v[cnt]=a*c;
            w[cnt]=b*c;
            cnt++;
        }//若用二进制优化后，仍然有余数，则在拿余数和之前的数，便可以表示1~c的所有整数
    }
    for(ll i=1;i<=cnt;i++)
    {
        for(ll j=m;j>=v[i];j--)
        {
            f[j]=max(f[j],f[j-v[i]]+w[i]);//01背包 
        }
    }
    cout<<f[m];
    return 0;
}