what is the maximum possible number of monsters you can defeat?

Question

Problem Statement:

While playing an RPG game, you were assigned to complete one of the hardest quests in this game. There are n monsters you'll need to defeat in this quest. Each monster i is described with two integer numbers - poweri and bonusi. To defeat this monster, you'll need at least poweri experience points. If you try fighting this monster without having enough experience points, you lose immediately.

You will also gain bonusi experience points if you defeat this monster. You can defeat monsters in any order. The quest turned out to be very hard - you try to defeat the monsters but keep losing repeatedly. Your friend told you that this quest is impossible to complete. Knowing that, you're interested, what is the maximum possible number of monsters you can defeat?

Input:

The first line contains an integer, n, denoting the number of monsters.

The next line contains an integer, e, denoting your initial experience.

Each line i of the n subsequent lines (where 0 ≤ i < n) contains an integer, poweri, which represents power of the corresponding monster.

Each line i of the n subsequent lines (where 0 ≤ i < n) contains an integer, bonusi, which represents bonus for defeating the corresponding monster.

Sample cases:

Input 2 123 78 130 10 0

Output 2

Output description

Initial experience level is 123 points. Defeat the first monster having power of 78 and bonus of 10. Experience level is now 123+10=133. Defeat the second monster.

What I have tried:

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));
    }

I am not getting correct answers with this solution. I thought of this problem as 0/1 knapsack problem( correct me If I am wrong). Also can you provide me DP solution of this problem.

Answer 1

You can just sort the monsters from lowest to highest power required and defeat them in that order.

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);
}