$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

结论： $f[i][j][k]=\max(f[i-1][j][k],f[i-1][j-v_1[i]][k-v_2[i]]+1)$

二维费用 01 背包思路：

• $1. 状态表示$
  $集合：只从前\ i\ 个里面选，费用1\ 不能超过\ j，费用2\ 不能超过\ k\ 的价值$
  $属性：\max$

• $2. 状态转移$
  $不选第\ i\ 个物品：f[i-1][j][k]$
  $选择第\ i\ 个物品：f[i-1][j-v_1[i]][k-v_2[i]]+1$

• $3. 滚动数组$
  $由于\ f[i][j][k]\ 只需用到当前层和上一层，则结论可转化为：$
  $f[j][k]=\max(f[j][k],\ f[j-v_1[i]][k-v_2[i]]+1)$

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 1010, M = 510;

int V1,V2,n;
int f[N][M]; //只从前 i 个里面选，费用1 不能超过 j，费用2 不能超过 k 的最大价值

int main()
{
    cin>>V1>>V2>>n;

    for(int i=1;i<=n;i++)
    {
        int v1,v2;
        cin>>v1>>v2;
        for(int j=V1;j>=v1;j--)
            for(int k=V2;k>=v2;k--)
                f[j][k]=max(f[j][k],f[j-v1][k-v2]+1);
    }

    //在价值最大的情况下，费用2 最少是多少
    int k=V2-1;
    while(k>0&&f[V1][k-1]==f[V1][V2-1]) k--;

    cout<<f[V1][V2-1]<<' '<<V2-k<<endl;

    return 0;
}