时间戳

首页 > 解决方案 > 您可以击败的最大怪物数量是多少？

java - 您可以击败的最大怪物数量是多少？

问题描述

问题陈述：

在玩 RPG 游戏时，您被分配完成该游戏中最困难的任务之一。n在此任务中，您需要击败一些怪物。每个怪物i都用两个整数描述 -poweri和bonusi。要打败这个怪物，你至少需要 poweri 经验值。如果你在没有足够经验值的情况下尝试与这个怪物战斗，你会立即失败。

bonusi如果你打败了这个怪物，你也会获得经验值。您可以按任何顺序击败怪物。结果证明任务非常艰巨-您试图击败怪物，但不断失败。你的朋友告诉你这个任务是不可能完成的。知道了，你有兴趣，你可以打败的怪物的最大可能数量是多少？

输入：

第一行包含一个整数 n，表示怪物的数量。

下一行包含一个整数 e，表示您的初始体验。

n 后续行（其中 0 ≤ i < n）中的每一行 i 都包含一个整数 poweri，它表示相应怪物的力量。

n 后续行（其中 0 ≤ i < n）中的每一行 i 包含一个整数 Bonusi，它表示击败相应怪物的奖励。

示例案例：

输入 2 123 78 130 10 0

输出2

输出说明

初始经验等级为123点。击败第一个力量78，加成10的怪物。经验等级现在是123+10=133。击败第二个怪物。

我试过的：

public static  int defeat(int [] monster,int bonus[],int n,int exp){
        if(n==0)
            return 0;
        
        if(n==1 && monster[0]<=exp)return 1;
        if(n==1 && monster[0]>exp) return 0;

        if(monster[n-1]<=exp){
            return defeat(monster,bonus,n-1,bonus[n-1]+exp )+ defeat(monster,bonus,n-1,exp);
        }else{
            return defeat(monster,bonus,n-1,exp);

        }


    }


    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int exp = s.nextInt();
        int monst[] = new int[n];
        int bonus[] = new int[n];
        for (int i = 0; i < n; i++) {
            monst[i] = s.nextInt();
        }
        for (int i = 0; i < n; i++) {
            bonus[i] = s.nextInt();
        }
        System.out.println(defeat(monst,bonus,n,exp));
    }

我没有得到这个解决方案的正确答案。我认为这个问题是 0/1 背包问题（如果我错了，请纠正我）。你也可以为我提供这个问题的DP解决方案。

标签： javadynamic-programming

解决方案

您可以将怪物从所需的最低功率到最高功率进行排序，然后按此顺序击败它们。

public static void main(String[] args) {
    Scanner s = new Scanner(System.in);
    int n = s.nextInt();
    int exp = s.nextInt();
    int monst[] = new int[n];
    int bonus[] = new int[n];
    for (int i = 0; i < n; i++) {
        monst[i] = s.nextInt();
    }
    for (int i = 0; i < n; i++) {
        bonus[i] = s.nextInt();
    }
    class Monster {
        private final int power, bonus;
        public Monster(int power, int bonus){
            this.power = power;
            this.bonus = bonus;
        }
    }
    Monster[] monsters = new Monster[n];
    for(int i = 0; i < n; i++) monsters[i] = new Monster(monst[i], bonus[i]);
    Arrays.sort(monsters, Comparator.comparingInt(m -> m.power));
    int count = 0;
    for(Monster m: monsters){
        if(exp < m.power) break;
        exp += m.bonus;
        ++count;
    }
    System.out.println(count);
}

推荐阅读