宠物小精灵之收服 （二维01背包）

【题目链接】

　　　　http://noi.openjudge.cn/ch0206/4978/

【算法】

　　　　做的第一道二维的背包问题，只需开的数组增加一维以正确表述每一个状态即可。本质还是多过程决策+最优子结构+无后效性。

【代码】

#include <bits/stdc++.h>
using namespace std;
int n,m,k,i,j,t,minm;
int v[1010],u[510],dp[1010][510];
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    minm=m;
    for(i=1;i<=k;i++) scanf("%d%d",&v[i],&u[i]);
    for(i=1;i<=k;i++)
        for(j=n;j>=v[i];j--)
            for(t=m;t>=u[i];t--)
                dp[j][t]=max(dp[j][t],dp[j-v[i]][t-u[i]]+1);
    for(i=0;i<=n;i++)
        for(j=0;j<=m;j++)
            if(dp[i][j]==dp[n][m]&&j<minm) minm=j;
    printf("%d %d
",dp[n][m],m-minm);
    return 0;
}