背包问题：注意集合的表示（f[i][j]的表示的含义）以及集合的计算
易错点：赋初值——根据集合的实际意义来划分
优化问题：大部分的背包问题——体积是从大到小来划分（前一层的状态），多重背包问题1和3——体积从小到大计算,一般可以优化掉一维

AcWing 423. 采药
直接用01背包的模型

#include<iostream>

using namespace std;

const int N = 1010;

int f[N],n,m;
int w[N],v[N];

int main()
{
    cin >> m >> n;
    for(int i=1;i<=n;i++)cin >> w[i] >> v[i];
    for(int i=1;i<=n;i++)
        for(int j=m;j>=w[i];j--)
            f[j]=max(f[j],f[j-w[i]]+v[i]);
    cout << f[m] << endl;
    return 0;
}

AcWing 1024. 装箱问题
不同点：求的是最小剩余空间——等价于求最大可以装的体积
f[i][j]——表示的是所有从前i个物品中选，体积不超过j的可装最大体积

#include<iostream>

using namespace std;

const int N = 2e4+10;

int f[N],n,m;

int main()
{
    cin >> n >> m;
    while(m--)
    {
        int a;
        cin >> a;
        for(int i=n;i>=a;i--)
            f[i]=max(f[i],f[i-a]+a);
    }
    cout << n-f[n] << endl;
    return 0;
}

AcWing 8. 二维费用的背包问题
限制条件变为了两个——体积和重量，f[i][j][k]表示所有在前i个物品中选，体积不超过j,重量不超过k的最大价值
集合计算(一般都是在边界位置，判断第i个物品选或者不选)——f[i-1][j][k],f[i-1][j-v][k-m]+w在两个中取一个最值，当然如果选择的话需要满足条件才可以选择这个物品，因此在这里我们选择体积和重量都从大到小来枚举

#include<iostream>

using namespace std;

const int N = 1010;

int f[N][N];
int n,v,m;

int main()
{
    cin >> n >> v >> m;
    while(n--)
    {
        int a,b,c;
        cin >> a >> b >> c;
        for(int i=v;i>=a;i--)
            for(int j=m;j>=b;j--)
                f[i][j]=max(f[i][j],f[i-a][j-b]+c);
    }
    cout << f[v][m] << endl;
    return 0;
}

AcWing 1022. 宠物小精灵之收服
和上一个题的模型相同 这里需要判断边界——体积为0的时候那个宠物无法捕捉

#include<iostream>

using namespace std;

const int N = 1010;

int f[N][N];
int n,m,k;

int main()
{
    cin >> n >> m >> k;
    while(k--)
    {
        int a,b;
        cin >> a >> b;
        for(int i=n;i>=a;i--)
            for(int j=m-1;j>=b;j--)
                f[i][j]=max(f[i][j],f[i-a][j-b]+1);
    }

    cout << f[n][m-1] << " ";

    int k=m-1;
    while(k>0&&f[n][k-1]==f[n][m-1])k--;
    cout << m-k << endl;
    return 0;
}

AcWing 278. 数字组合
注意初始值f[0][0]=1;
f[i][j]==f[i-1][j],f[i-1][j-v[i]]首先第一种情况一定存在，第二种情况有的时候存在，因此需要考虑完整
用二维写法——可以仔细地描述情况，优化写法只是对代码做一个等价变形

#include<iostream>

using namespace std;

const int N = 1e4+10, M= 110;

int f[M][N];
int n,m,v[M];

int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++)cin >> v[i];

    f[0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
        {
            f[i][j]=f[i-1][j];
            if(j>=v[i])f[i][j]+=f[i-1][j-v[i]];
            //不能直接写在一起，但在一维优化的时候可以写在一起
        }

    cout << f[n][m] << endl;
    return 0;
}

AcWing 1023. 买书
完全背包的方案数：优化为1维的遇上一个题类似
注意初始值f[0][0]=1;

#include<iostream>

using namespace std;

const int N = 1010;

int f[N];
int m,v[4]={10,20,50,100};

int main()
{
    cin >> m;
    f[0]=1;
    for(int i=0;i<4;i++)
        for(int j=v[i];j<=m;j++)
            f[j]+=f[j-v[i]];
    cout << f[m] << endl;
    return 0;
}