01背包问题

• 最多收服多少个小精灵

根据题意我们发现，题中给出了类似于两个背包容量的值

1. 小智的精灵球数量
2. 皮卡丘初始的体力值

因此，我们可以将本题转换为01背包问题(三维数组)
题目要求最终求出的是最多收服多少个小精灵，以及收服N个小精灵时皮卡丘的剩余体力值最多为多少
因此，我们可以设定一个状态转移方程:
i：在前i个小精灵中进行捕捉
j：所用的精灵球数量小于 j
z：总共消耗的体力值小于 z
dp[i][j][z]:前 i 个小精灵中在所用球数小于 j 且消耗体力值小于 z 的情况下能捕捉小精灵数量的最大值

v1[i]:收服第 i 个小精灵需要的精灵球的数量
v2[i]:收服第 i 个小精灵过程中对皮卡丘造成的伤害

接下来就是分析方程的几种情况
不选i：dp[i][j][z] = dp[i-1][j][z]
选i：dp[i][j][z] = dp[i-1][j - v1[i]][z - v2[i]] + 1

注意：因为题目中说明当所消耗的体力等于皮卡丘的体力时，也是不能捕捉成功的，所以 z 的最大值即为皮卡丘的体力-1

• 皮卡丘最大剩余体力

dp[k][n][m - 1]：在所有小精灵中使用全部的精灵球且皮卡丘不挂的前提下所能捕捉小精灵的最大数量
因为要是皮卡丘剩余体力最大，所以我们可以倒序遍历第三维 m，即从可消耗最大体力来开始倒序遍历，那么当最多花费 m-1 体力时能捕捉最大小精灵的数量和使用 m 体力时能捕捉最大小精灵的数量 相同的话，即可证明皮卡丘可以省 1 点体力
以此类推，那么当全部遍历完成后，我们就可以得到皮卡丘可以节省的最大总体力数，再用皮卡丘的体力 - 可以节省的最大总体力数 = 最大剩余体力数

三维数组 + 动态规划
这种解法看起来通俗易懂，但是会爆内存，因此可以先将最朴素的写法列出再进行优化

public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();//小智的精灵球数量
        int m = scan.nextInt();//皮卡丘初始的体力值
        int k = scan.nextInt();//野生小精灵的数量


        int[] v1 = new int[k+5];//收服该小精灵需要的精灵球的数量
        int[] v2 = new int[k+5];//收服过程中对皮卡丘造成的伤害

        for(int i=1; i<=k; i++){
            v1[i] = scan.nextInt();
            v2[i] = scan.nextInt();
        }

        int[][][]dp = new int[k+5][n+5][m+5];//前i个小精灵中选取的球数小于j并且占用空间小于z的可选的最大数量


        for(int i=1; i<=k; i++){
            for(int j=0; j<=n; j++){
                for(int z=0; z<=m-1; z++){
                    dp[i][j][z] = dp[i-1][j][z];
                    if(j >= v1[i] && z>=v2[i]){
                        dp[i][j][z] = Math.max(dp[i][j][z], dp[i-1][j-v1[i]][z-v2[i]] + 1);   
                    }
                }
            }
        }

        int k1 = m - 1;

        while(k1 > 0 && dp[k][n][k1 - 1] == dp[k][n][m - 1]){
            k1--;   
        }

        System.out.println(dp[k][n][m-1] + " " + (m - k1));
    }
}

优化：二维数组 + 动态规划
即将第一维的 i 进行删除即可

public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();//小智的精灵球数量
        int m = scan.nextInt();//皮卡丘初始的体力值
        int k = scan.nextInt();//野生小精灵的数量


        int[] v1 = new int[k+5];//收服该小精灵需要的精灵球的数量
        int[] v2 = new int[k+5];//收服过程中对皮卡丘造成的伤害

        for(int i=1; i<=k; i++){
            v1[i] = scan.nextInt();
            v2[i] = scan.nextInt();
        }

        int[][]dp = new int[n+5][m+5];//前i个小精灵中选取的球数小于j并且占用空间小于z的可选的最大数量


        for(int i=1; i<=k; i++){
            for(int j=n; j>=v1[i]; j--){
                for(int z=m-1; z>=v2[i]; z--){
                    dp[j][z] = Math.max(dp[j][z], dp[j-v1[i]][z-v2[i]] + 1);
                }
            }
        }

        int k1 = m - 1;

        while(k1 > 0 && dp[n][k1 - 1] == dp[n][m - 1]){
            k1--;   
        }

        System.out.println(dp[n][m-1] + " " + (m - k1));
    }
}