一：多重背包

1.朴素做法：
4. 多重背包问题 I

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e2+5;
typedef long long ll;
const int mod=1e9+7;
typedef  unsigned long long ull;
//typedef __int128 LL;
const double eps=10e-8;
const double pi=acos(-1.0);
#define between(x,a,b)(a<=x && x<=b)
const int inf=0x3f3f3f3f;
const long long INF=0x3f3f3f3f3f3f3f3f;
typedef pair<ll,ll> pII;
typedef pair<int,int> pii;
typedef pair<int,ll> piI;
int v[MAXN],w[MAXN],s[MAXN];
int dp[MAXN];
int main()
{
#ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);
    freopen("debug.out", "w", stdout);
#endif
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d%d%d",&v[i],&w[i],&s[i]);
    memset(dp,0xcf,sizeof dp);
    dp[0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=s[i];j++)//把所有的物品分来，看成不同的
        {
            for(int k=m;k>=v[i];k--)
            {
                dp[k]=max(dp[k],dp[k-v[i]]+w[i]);
            }
        }
    }
    int ans=0;
    for(int i=0;i<=m;i++)ans=max(ans,dp[i]);
    printf("%d\n",ans);

    return 0;
}

2.二进制优化：
5. 多重背包问题 II
ci为物品个数
ci
2^0+2^1+2^2+…+2^p<=ci
剩下：ri=ci-(2^0+2^1+2^2+…+2^p)
2^0 2^1 2^2 2^3 … 2^p ri
ri+2^0 ri+2^1 ri+2^0+2^1 … ri+^0+2^1+2^2+…+2^p=ri+2^(p+1)-1=ci 所以可以用来表示ri~ci之间的数
2^0 2^1 2^2 2^3 … 2^p 可以表示 0~2^(p+1)-1 之间的数
2^0+2^1+2^2+…+2^p<=ci再加2^(p+1)超过ri 说明ri<2^(p+1)
[0 ~ 2^(p+1)-1]
[ri ~ ci]
[0 ~ [ri ~ 2^(p+1)-1] ~ ci]

可以表示所有[0~ci]的数

#include <bits/stdc++.h>
using namespace std;
const int MAXN=2e3+5;
typedef long long ll;
const int mod=1e9+7;
typedef  unsigned long long ull;
//typedef __int128 LL;
const double eps=10e-8;
const double pi=acos(-1.0);
#define between(x,a,b)(a<=x && x<=b)
const int inf=0x3f3f3f3f;
const long long INF=0x3f3f3f3f3f3f3f3f;
typedef pair<ll,ll> pII;
typedef pair<int,int> pii;
typedef pair<int,ll> piI;
int v[MAXN],w[MAXN],s[MAXN];
int dp[MAXN];
int main()
{
#ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);
    freopen("debug.out", "w", stdout);
#endif
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&v[i],&w[i],&s[i]);

    }
    memset(dp,0xcf,sizeof dp);
    dp[0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=s[i];j*=2)
        {
            s[i]-=j;
            for(int k=m;k>=v[i]*j;k--)
            {
                dp[k]=max(dp[k],dp[k-v[i]*j]+w[i]*j);
            }
        }
        if(s[i]>0)
        {
            for(int k=m;k>=v[i]*s[i];k--)
            {
                dp[k]=max(dp[k],dp[k-v[i]*s[i]]+w[i]*s[i]);
            }
        }
    }
    int ans=0;
    for(int i=0;i<=m;i++)ans=max(ans,dp[i]);
    printf("%d\n",ans);

    return 0;
}

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=2010;
#include<vector>
int n,m;
int f[N];

struct Good
{
    int v,w;
};
int main()
{
    vector<Good>goods;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        int v,w,s;
        cin>>v>>w>>s;
        for(int k=1;k<=s;k*=2)
        {
            s-=k;
            goods.push_back({v*k,w*k});
        }
        if(s>0)goods.push_back({v*s,w*s});
    }
    for(auto good:goods)
        for(int j=m; j>=good.v; j--)
        f[j]=max(f[j], f[j-good.v]+good.w);
    cout<<f[m]<<endl;
    return 0;

}

二：分组背包：

9. 分组背包问题

 #include <bits/stdc++.h>
using namespace std;
const int MAXN=2e2+5;
typedef long long ll;
const int mod=1e9+7;
typedef  unsigned long long ull;
//typedef __int128 LL;
const double eps=10e-8;
const double pi=acos(-1.0);
#define between(x,a,b)(a<=x && x<=b)
const int inf=0x3f3f3f3f;
const long long INF=0x3f3f3f3f3f3f3f3f;
typedef pair<ll,ll> pII;
typedef pair<int,int> pii;
typedef pair<int,ll> piI;
int v[MAXN][MAXN],w[MAXN][MAXN],s[MAXN];
int dp[MAXN];
int main()
{
#ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);
    freopen("debug.out", "w", stdout);
#endif
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&s[i]);
        for(int j=1;j<=s[i];j++)
        {
            scanf("%d%d",&v[i][j],&w[i][j]);
        }

    }
    memset(dp,0xcf,sizeof dp);
    dp[0]=0;
    for(int i=1;i<=n;i++)//阶段
    {
        for(int j=m;j>=0;j--)//状态
        {
            for(int k=1;k<=s[i];k++)//决策 每个组里面选择一个最优的
            {
                if(j>=v[i][k])dp[j]=max(dp[j],dp[j-v[i][k]]+w[i][k]);
            }
        }
    }
    int ans=0;
    for(int i=0;i<=m;i++)ans=max(ans,dp[i]);
    printf("%d\n",ans);

    return 0;
}