多重背包

链接：https://ac.nowcoder.com/acm/problem/235950 来源：牛客网

做法：适用于物品数量不是无限但又不止一个的背包问题，一开始想到的是将n个相同重量的物品当作n个不同的物品，但完全背包的复杂度已经汗流浃背，所以我们需要把这个重复的n进行优化，我们尽量去把2的幂作为一组进行打包，剩下的再作为一组打包，这样我们就能用我们构造的数去凑出任何一个1到n之间的数（拆位），那么之后就是经典01背包，这里用嵌套pair去存储（懒。

//本题代码
#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
//dont forget to check long long
//别写重变量名
//记得判越界
//别死磕
//处理字符串删掉关流
std::vector<std::pair<int,std::pair<int,int>>> a;
int f[510000];
void op(int x,int w,int v)
{
    int u=0;
    int xx=x;
    while(xx)
    {
        if((1<<u)<=xx)
        {
            //std::cout<<(1<<u)<<" "<<xx<<endl;
            a.push_back({(1<<u),{w,v}});
            xx-=(1<<u);
            u++;
        } 
        else break;
    }
    //std::cout<<xx<<endl;
    a.push_back({xx,{w,v}});
}
void slove()
{
    int n,m;
    std::cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int x,w,v;
        std::cin>>x>>w>>v;
        op(x,w,v);
    }
    f[0]=0;
    for(int i=0;i<(int)a.size();i++)
    {
        for(int j=m;j>=a[i].first*a[i].second.first;j--)
        {
            if(j>=a[i].first*a[i].second.first)
            f[j]=std::max(f[j],f[j-a[i].first*a[i].second.first]+a[i].first*a[i].second.second);
        }
    }
    std::cout<<f[m]<<endl;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int T=1; 
    //std::cin>>T;
    while(T--)    {
        slove();
    }

    return 0;
}