算法分析

二维费用01背包问题

• 花费1：精灵球数量

• 花费2：皮卡丘体力值

• 价值：小精灵的数量(每只精灵价值为1)

• 状态表示：f[i,j,k]表示所有只考虑前i个物品，且花费1不超过j，花费2不超过k的选法的最大值

• 状态计算：f[i,j,k] = Max(f[i - 1,j,k],f[i - 1,j - v1[i],k - v2[i]] + 1)

最大收服的小精灵的数量f[K,N,M]
在收拾最大数量时，消耗的最少体力，从K - 1开始枚举到0，找出收服数量为f[k,N,M]的最小k值

注意：题目说道：使得皮卡丘体力小于等于0的野生小精灵也不会被小智收服，因此皮卡丘的体力值需在V2 - 1时开始

时间复杂度 $O(KNM)$

参考文献

算法提高课

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 1010;
    static int M = 510;
    static int[][] f = new int[N][M];
    static int n;
    static int V1;//精灵球数量
    static int V2;//皮卡丘体力值
    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = reader.readLine().split(" ");
        V1 = Integer.parseInt(s1[0]);
        V2 = Integer.parseInt(s1[1]);
        n = Integer.parseInt(s1[2]);
        for(int i = 1;i <= n;i++)
        {
            String[] s2 = reader.readLine().split(" ");
            int v1 = Integer.parseInt(s2[0]);
            int v2 = Integer.parseInt(s2[1]);
            for(int j = V1;j >= v1;j--)
                for(int k = V2 - 1;k >= v2;k--)
                {
                    f[j][k] = Math.max(f[j][k], f[j - v1][k - v2] + 1);
                }
        }
        int k = V2 - 1;//找到当前皮卡丘消耗体力最少的情况
        while(k > 0 && f[V1][k - 1] == f[V1][V2 - 1]) k--;
        System.out.println(f[V1][V2 - 1] + " " + (V2 - k));
    }
}