AcWing 5. 多重背包问题 II（二进制优化）

题目链接

https://www.acwing.com/problem/content/5/

思路 part1

受了完全背包和01背包的启发我们不难想到，一种高效的方法来优化，我们讲物品的次数做一个二进制拆分（不足的就用余数来补齐），那么对于这个拆分出来的这些次数我们就将其转化为一件“大”物品，那么我们单独堆这个拆分出来的值进行一个01背包，那么我们就能组合出 [ 0 , s [ i ] ] [0,s[i]] [0,s[i]]范围内所有的情况，选或者不选嘛，那么我们对所有的物品都这样拆分，最终再跑一个01背包就好啦

part2

当然如果你觉得这样空间复杂度很高，那么我们可以直接再拆分的时候跑01背包，注意这里为什么能先枚举次数再枚举体积，其实我们这里枚举的并不是次数，而是一个物品，你要理解一下，只不过看着像枚举的次数，实际上我们做的操作就是枚举一个物品，所以这样写也是对的

代码 直接二进制拆分

#include
using namespace std;

const int N = 2e4+10;
int n,V;
int v[N],w[N],f[N];


int main()
{
    cin>>n>>V;
    int a,b,c;
    int cnt = 0;
    for(int i = 1;i >a>>b>>c;
        for(int num = 1;c;numv[i]>>w[i]>>s[i];
    
    for(int i = 1;i  0; k = v[i] * k; --j)
                f[j] = max(f[j],f[j-v[i] * k] + w[i] * k);
        }
    }
    cout