tip

这次分享的方法对于已经完全会背包问题的人来说很麻烦,也很愚蠢。
仅供初学者记忆

引入

众所周知，AcWing首页前几题都是背包问题，而算法都是DP
其实，我素来只记住多重背包问题II，而其他问题却迎刃而解
首先，我们来看看多重背包问题II的代码：
题解

#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;
}

不难发现，我们可以将01背包换成数量为1的多重背包问题II来做
代码

#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=1;//数量：1
        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;
}

接下来是完全背包
由于总体积为m，每个物品的体积为v[i]，那么背包内最多可放入m/v[i]个物品（应该很好理解😀）
代码

#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=m/a;//数量：m/a（v[i]）
        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;
}

然后多重背包问题I，完全可以直接使用多重背包问题II的代码

接着是多重背包问题III

tip

此代码附带卡常，比赛禁止使用！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

#include <iostream>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#pragma GCC optimize(5)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("Os")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll N=1e4*2+100;
ll n,m;
ll a,b,c;
ll f[N];
ll v[N],w[N];
ll cnt=1;
signed main()
{
    cin>>n>>m;
    for(ll i=1;i<=n;i++)
    {
        cin>>a>>b>>c;
        ll k=1;
        while(k<=c)
        {
            v[cnt]=k*a;
            w[cnt]=k*b;
            cnt++;
            c-=k;
            k*=2;
        }
        if(c!=0)
        {
            v[cnt]=c*a;
            w[cnt]=c*b;
            cnt++;
        }
    }
    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]);
        }
    }
    cout<<f[m];
    return 0;
}

最后是我们的混合背包
数量只要按照判定好类型后加以改正即可

#include <bits/stdc++.h>
using namespace std;
int n,m,v[100010],w[100010],f[100010];
int main()
{
    cin>>n>>m;
    int cnt=1;
    for(int i=1;i<=n;i++)
    {
        int a,b,s;
        cin>>a>>b>>s;
        int k=1;
        if(s<0)s=1;
        else if(s==0)s=m/a;//把01背包和多重背包先转化成多重背包，若为完全背包，则在最优情况下，只能取总体积/该物品体积向下取整 
        while(k<=s)
        {
            v[cnt]=a*k;
            w[cnt]=b*k;
            s-=k;
            k*=2;
            cnt++;
        }
        if(s>0)
        {
            v[cnt]=s*a;
            w[cnt]=s*b;
            cnt++;
        }
    }//将多重背包进行二进制优化，变成01背包 
    for(int i=1;i<=cnt;i++)
    {
        for(int j=m;j>=v[i];j--)
        {
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }//01背包问题
    cout<<f[m]<<endl;
    return 0;
}