状态表示

f[i][j][l]表示在前i个精灵，精灵球有j个，皮卡丘血量有l时的最大捕获数量；

w[i]表示捕获需要皮卡丘消耗的血量；

v[i]表示捕获需要消耗的精灵球的数量；

状态转移方程

f[i][j][l]=max(f[i-1][j][l],f[i-1][j-v[i]][l-w[i]]+1);

滚动数组优化

应为每次只涉及到第i个之前的问题，所以可以优化为

f[j][l]表示在精灵球有j个，皮卡丘血量有l时的最大捕获数量；

f[j][l]=max(f[j][l],f[i-v[i]][l-w[i]]+1);

C++代码

#include<bits/stdc++.h>
using namespace std;
const int N=1010,M=510,K=110;
int f[N][M],v[K],w[K];
int main()
{
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++) cin>>v[i]>>w[i];
    //计算在前i个精灵，精灵球有j个，皮卡丘血量有l时的最大捕获数量；
    for(int i=1;i<=k;i++)
        for(int j=n;j>=1;j--)
            for(int l=m-1;l>=1;l--)//应为皮卡丘最少要剩下一滴血才能收复对方，所以从m-1开始；
                if(j>=v[i]&&l>=w[i])
                    f[j][l]=max(f[j][l],f[j-v[i]][l-w[i]]+1);
    //通过遍历寻找收复最多的精灵数量，所使用的最小血量
    int t,cnt=f[n][m-1];
    for(int i=m;i>=0;i--) if(f[n][i]==cnt) t=i;

    cout<<cnt<<" "<<m-t<<endl; 
    return 0;
}