您最多可以打败多少怪物？

Question

问题陈述：

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

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

输入：

第一行是一个整数n，表示怪物的数量

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

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

n行中的每一行i（其中0≤i

样本案例：

输入 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解决方案吗？

Answer 1

你可以把怪物从最低到最高所需的力量排序，然后按这个顺序打败它们。

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

Answer 2

也许我太简单了，但我会尝试如下：

首先像这样创建一个classMonster：

public class Monster
{
  final int m_Power;
  final int m_Bonus;

  public Monster( final int power, final int bonus )
  {
    m_Power = power;
    m_Bonus = bonus;
  }

  public final int getPower() { return m_Power; }
  public final int getBonus() { return m_Bonus; }
}

接下来，像这样初始化一个怪物列表：

public static void main( String... args ) 
{ 
  final var scanner = new Scanner( System.in );
  final var n = scanner.nextInt();
  final var experience = scanner.nextInt();
  final var power [] = new int [n];
  for( var i = 0; i < n; ++i ) 
  {
    power [i] = scanner.nextInt();
  }
  List<Monster> monsters = new ArrayList<>( n );
  for( var i = 0; i < n; ++i ) 
  {
    monsters.add( new Monster( power [i], scanner.nextInt();
  }
  monsters.sort( (m1,m2) ->
  { 
    final var p = m1.getPower() - m2.getPower();
    return p == 0 ? m2.getBonus() - m1.getBonus(() : p; 
  } ); //*1
  System.out.println( defeat( monsters, experience ) );
}

*1 -> 此比较器的实现仅适用于与 MAX_INT 相比较小的功率和奖励值。

列表monsters现在包含按强度升序排列的怪物；具有相同力量的怪物按其奖励值降序排列。

现在我对 defeat() 的实现如下所示：

public final int defeat( final List<Monster> m, final int initialExperience )
{
  var experience = initialExperience;
  var retValue = 0;
  final Stack<Monster> monsters = new LinkedList<>( m );
  while( !monsters.empty() )
  {
    var monster = monsters.pop();
    if( experience > monster.getPower() )
    {
      experience += monster.getBonus();
      ++retValue;
    }
    else break;
  }
  return retValue;
}

Answer 3

            n=int(input())
            e=int(input())
            P=[]
            for i in range(n):
                P.append(int(input()))
            B=[]
            for i in range(n):
                B.append(int(input()))
            c=0
            f=True
            while n>0 and f:
                f=False
                i=0
                while i<n:
                    if e>=P[i]:
                        e+=B[i]
                        P.pop(i)
                        B.pop(i)
                        n-=1 
                        c+=1
                        f=True
                        i-=1
                    i+=1
            print(c)

Answer 4

import java.io.*;
import java.util.*;

class Player {
    int exp;

    public int getExp() {
        return exp;
    }

    public void setExp(int exp) {
        this.exp = exp;
    }
}

class Monster {
    int power;
    int bonus;

    public int getPower() {
        return this.power;
    }

    public int getBonus() {
        return this.bonus;
    }

    public void setBonus(int bonus) {
        this.bonus = bonus;
    }

    public void setPower(int power) {
        this.power = power;
    }
}

class Calc {
    public int calc() {

        Scanner sc = new Scanner(System.in);
        //number of monsters
        System.out.println("enter the number of monsters");
        int n = sc.nextInt();
        int arr[] = new int[n];
        System.out.println("enter the power of the player");
        Player player = new Player();
        player.setExp(sc.nextInt());
        //declaration of array type object of monster
        Monster monster[] = new Monster[n];
        //value setting completed
        for (int i = 0; i < n; i++) {
            //allocation of object to the real
            monster[i] = new Monster();
            System.out.println("enter the power of monster");
            monster[i].setPower(sc.nextInt());
            System.out.println("enter the bonus that to be earned after killing the monster");
            monster[i].setBonus(sc.nextInt());
        }
        //calculate win or loose
        int count = 0;
        int flag = 0;
        //**
        for (int i = 0; i < n; i++) {
            if (player.getExp() >= monster[i].getPower()) {
                player.setExp(player.getExp() + monster[i].getBonus());
                count = count + 1;
                // flag = flag + 1;
            } else if (player.getExp() < monster[i].getPower()) {
                for (int j = 0; j < n; j++)
                    arr[j] = i;
                //count = count;
                flag = flag + 1;
            }
            //**
            for (int t = 0; t < flag; t++) {
                if (player.getExp() >= monster[arr[t]].getPower()) {
                    count = count + 1;
                }

            }
        }
        return count;
    }

}

public class Main {
    public static void main(String[] args) {
        // write your code here
        System.out.println("welcome to the loosing game");
        Calc c = new Calc();
        System.out.println("no of monster killed" + c.calc());
    }
}

您最多可以打败多少怪物？

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

java

dynamic-programming