再对比 \(f[i][j-v[i]]\) ：

我们发现两个式子很像，不过，\(f[i][j-v[i]]\) 多了一项 \(f[i-1][j-(s[i]+1)w[i]]+s[i]×w[i])\) ，我们不可以通过前 \(n\) 个数的最大值和最后一个数，求出前 \(n-1\) 个数的最大值，所以这样的方法是不可行的

我们可以用二进制的方式来优化例如当 \(s=1023\) 时，我们真的需要从 \(0\) 枚举到 \(1023\) 吗？我们可以将若干个 \(i\) 个物品打包，比如说我们可以打包成10组：\(1,2,4,8,...512\)每组最多选一次，我们可以用这10组凑出来 \(0\) 到 \(1023\) 的任何数（二进制可以表示出所有的十进制整数）

那么对于任何一个 \(s\)，我们将物品打包成 \(2^0,2^1,2^2,...,2^k\)，\(2^0\) 一直加到 \(2^k \leq s\)如果 \(2^0\) 一直加到 \(2^k < s\)，再补上一个 \(c\)那么显然有 \(c<2^{k+1}\)那么来证明一下是不是这样就能表示出 \(0\) 到 \(s\) 的所有数？首先，\(2^0\) 一直加到 \(2^k\) 能凑出 \(0\) 到 \(2^{k+1}-1\) 的所有数（等比数列公式）补上 \(c\) 以后便能凑出 \(0\) 到 \(2^{k+1}+c\) 的所有数，\(2^{k+1}+c\) 即 \(s\)所以是可行的，我们将原本的 \(O(m^2 n)\) 优化到了 \(O(m^2 logn)\)转化完之后再求一遍01背包就行了注意我们的打包时数组体积的部分要开 \(log_2 2000×1000\) \(log_22000\) 要上取整得 \(12\)

#include using namespace std;const int N = 25000;int n,m;int v[N],w[N],f[N];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; //2的k次幂        while(k<=s)        {            cnt++;            v[cnt]=a*k;            w[cnt]=b*k;            s-=k;            k*=2;        }        //补上的c        if(s>0)        {            cnt++;            v[cnt]=a*s;            w[cnt]=b*s;        }    }    n=cnt;    for(int i=1;i<=n;i++)        for(int j=m;j>=v[i];j--)            f[j]=max(f[j],f[j-v[i]]+w[i]);    cout<

其实还有单调队列的优化方式，不过是提高的内容，等我之后滚回来更新

分组背包

Acwing 9 分组背包问题

状态表示：二维集合：只从前 \(i\) 个物品里面选，且总体积 \(\leq j\) 的所有选法属性：选法价值的最大值

状态计算：枚举第 \(i\) 组，物品选第几个或不选不选也就是 \(f[i-1][j]\)选第 \(k\) 个也就是 \(f[i-1][j-v[i][k]]+w[i][k]\)注意 \(k\) 枚举的是下标，所以从0开始

#include using namespace std;const int N = 105;int f[N][N],v[N][N],w[N][N],s[N];int n,m;int main(){    cin>>n>>m;    for(int i=1;i<=n;i++)     {        cin>>s[i];        for(int j=0;j>v[i][j]>>w[i][j];    }    for(int i=1;i<=n;i++)    {        for(int j=0;j<=m;j++)        {            f[i][j]=f[i-1][j];            for(int k=0;k

直接删去一维，得到状态转移方程

#include using namespace std;const int N = 105;int f[N],s[N],v[N][N],w[N][N];int n,m;int main(){    cin>>n>>m;    for(int i=1;i<=n;i++)    {        cin>>s[i];        for(int j=0;j>v[i][j]>>w[i][j];    }    for(int i=1;i<=n;i++)        for(int j=m;j>=0;j--)            for(int k=0;k

#include #include using namespace std;const int N = 1010;int f[N];struct Thing{    int kind,v,w;};vector things;int main(){    int n,m;    cin>>n>>m;    for(int i=1;i<=n;i++)    {        int v,w,s;        cin>>v>>w>>s;        if(s==-1) things.push_back({0,v,w});        else if(s==0) things.push_back({1,v,w});        else        {            int k=1;             while(k<=s)            {                things.push_back({0,v*k,w*k});                s-=k;                k*=2;            }            if(s>0) things.push_back({0,v*s,w*s});        }    }    for(auto thing:things)    {        if(thing.kind==0)        {            for(int j=m;j>=thing.v;j--)             {                f[j]=max(f[j],f[j-thing.v]+thing.w);            }        }        else        {            for(int j=thing.v;j<=m;j++)             {                f[j]=max(f[j],f[j-thing.v]+thing.w);            }        }    }    cout<