01背包：每个物品：选、不选

完全背包：每个物品：选0，选1个，选2个...（求所有前缀的最大值）

多重背包：每个物品：选0，...选si个（求滑动窗口的最大值）

采药题目链接

423. 采药 - AcWing题库

采药代码

#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010;
int n,m;
int f[N];
int main(){
    cin >> m >> n;
    for(int i=0;i<n;++i)
    {
        int v,w;
        cin>>v>>w;
        for(int j=m;j>=v;j--)
        {
            f[j]=max(f[j],f[j-v]+w);
        }
    }
    printf("%d\n",f[m]);
    return 0;
}

装箱题目链接

AcWing 1024. 装箱问题 - AcWing

装箱代码

#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 20010;
int m, n;
int f[N];
int main(){
    
    cin >> m >> n;
    for(int i=0;i<n;++i)
    {
        int v;
        cin>>v;
        for(int j=m;j>=v;j--)
        {
            f[j]=max(f[j],f[j-v]+v);
        }
    }
    printf("%d",m-f[m]);
    return 0;
}

宠物小精灵之收服题目链接

1022. 宠物小精灵之收服 - AcWing题库

宠物小精灵之收服题目解析

花费1：精灵球数量

花费2：皮卡丘体力值

价值：小精灵的数量

状态表示：f[i, j, k]表示所有只从前i个物品中选，且花费1不超过j，花费2不超过k的选法的最大价值。

状态计算：f[i, j, k] = max(f[i-1, j, k], f[i-1, j-v1[i], k-v2[i]] + 1)

最多收服的小精灵数量 f[K, N, K]

最少耗费体力 f[K, N, m] == f[K, N, M]

宠物小精灵之收服代码

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010, M = 510;

int n, V1, V2;
int f[N][M];
int main(){
    cin >> V1 >> V2 >> n;
    for(int i=0;i<n;++i)
    {
        int v1, v2;
        cin >> v1 >> v2;
        for(int j=V1;j>=v1;j--)
            for(int k=V2-1;k>=v2;k--)
                f[j][k]=max(f[j][k], f[j-v1][k-v2]+1);
    }
    cout << f[V1][V2-1] <<' ';
    int k = V2 - 1;
    while(k>0 &&f[V1][k-1]==f[V1][V2-1]) k--;
    cout << V2 - k <<endl;
        
    return 0;
}