题目链接：宠物小精灵之收服 - 洛谷
标签：dp、背包问题
思路：
精灵球个数 与 对皮卡丘的伤害 都可以看成背包问题中的体积，所以将dp数组升级为二维
dp[i][j]表示 i个精灵球 j滴血皮卡丘 最多可以收服多少小精灵。
得到转移方程 dp[i][j] = max(dp[i-v1][j-v2]+1,dp[i][j])
注意点：洛谷测评所用数据与题目描述不一致，将dp数组开成1005×5005才通过
AC代码：
#include<iostream>
using namespace std;
int dp[1005][5005];
int main()
{
int n,m,num;
cin>>n>>m>>num;
int v1,v2;
for(int i=1;i<=num;++i)
{
cin>>v1>>v2;
for(int j=n;j>=v1;j--)
{
for(int k=m;k>v2;k--)
{
dp[j][k]=max(dp[j][k],dp[j-v1][k-v2]+1);
}
}
}
if(dp[n][m]==0) cout<<"0 "<<m<<endl;
else for(int i=m;i>0;i--)
{
if(dp[n][i]<dp[n][m])
{
cout<<dp[n][m]<<" "<<m-i;
break;
}
}
return 0;
}
