一场有100个对手的比赛，赢尽可能多的钱

Question

你和 100 个对手玩游戏。游戏有 k 轮。每一轮你都可以消灭一些对手（总是至少 1 个）。消除它们将获得奖励。

奖励为：100.000 *“被淘汰的对手数量”/“对手数量”<= 整数（向下舍入）

我想以某种方式消灭对手，让我获得尽可能多的钱。

示例游戏：

回合数 = 3
第一轮我们淘汰了 50 个对手，所以我们得到 100.000 * 50 / 100 = +50.000
第二轮我们淘汰了 30 个，所以我们得到 100.000 * 30 / 50 = +60.000
上一轮我们淘汰了最后 20 个对手，所以我们得到 100.000 * 20 / 20 = +100.000
因此总奖金为：210.000

我试着写了一些东西，但我认为这不是最有效的方法？

Program EliminationGame;
var
  selectedHistory : array [1..10] of integer;
  opponentCount,roundCount : integer;
  maxOpponents,numberSelected : integer;
  totalMoney : integer;
  i : integer;
begin
  totalMoney := 0;
  maxOpponents := 100;
  opponentCount := maxOpponents;
  roundCount := 3; {test value}
  for i:=1 to roundCount do begin
    if (i = roundCount) then begin 
      numberSelected := opponentCount;
    end else begin
      numberSelected := floor(opponentCount / roundCount);
    end;
    selectedHistory[i] := numberSelected;
    totalMoney := floor(totalMoney + (numberSelected / opponentCount * 100000));
    opponentCount := opponentCount - numberSelected;
  end;
  writeln('Total money won:');
  writeln(totalMoney);
  writeln('Amount selected in rounds:');
  for i:= 0 to Length(selectedHistory) do
    write(selectedHistory[i],' ');
end.

另外pascal好像没有floor函数？

Answer 1

这个问题可以用动态的方法解决。

F(round,number_of_opponents_remained):
  res = 0
  opp // number_of_opponents_remained
  for i in [1 opp]
    res = max(res, opp/100 + F(round-1,opp - i) )
  return res

我应该说这不是完整的解决方案，您添加了一些相关细节，我只是给您一个想法。您应该添加一些细节，例如基本情况并检查是否 opp>0 和其他一些细节。这个算法的复杂度是O(100*k).

Answer 2

看来这道题有数学答案可以提前算出来。正如@Anton 所说，很明显，第三轮给出的分数与消灭敌人的数量无关。所以第三回合应该消灭1个敌人。

所以我们得到了下面的三轮游戏函数

f(x)=100000x/100+100000(99-x)/(100-x)+100000*1/1, where x- the number of enemies eleminated at first round.

如果我们找到极值（函数的局部最大值），它看起来等于 90。这意味着决定如下：第一轮消除 90，第二轮 - 9，第三轮 - 1 个敌人。当然，供考虑：90=100-sqrt(100).

换句话说：任务的Pascal决策是从1到99循环一个变量，看这个函数的最大值。 X-将是答案。

program Project1;


var
  x, xmax: byte;
  MaxRes, tmp: real;

begin
  xmax := 0;
  MaxRes := 0;
  for x := 1 to 99 do
  begin
    tmp := 100000 * x / 100 + 100000*(99 - x) / (100 - x) + 100000 * 1 / 1;
    if tmp > MaxRes then
    begin
      MaxRes := tmp;
      xmax := x;
    end;
  end;
writeln(xmax);
readln;
end.

其他敌人数量和轮数（使用递归）的一般决定如下（Delphi方言）：

program Project1;

{$APPTYPE CONSOLE}
{$R *.res}

Uses System.SysUtils;

var
  s: string;

function Part(RemainingEnemies: byte; Depth: byte;
  var OutputString: string): real;
var
  i: byte;
  tmp, MaxRes: real;
  imax: byte;
  DaughterString: string;
begin
  OutputString := '';
  if Depth = 0 then
    exit(0);
  imax := 0;
  MaxRes := 0;
  for i := 1 to RemainingEnemies - Depth + 1 do
  begin
    tmp := i / RemainingEnemies * 100000 + Part(RemainingEnemies - i, Depth - 1,
      DaughterString);
    if tmp > MaxRes then
    begin
      MaxRes := tmp;
      imax := i;
      OutputString := inttostr(imax) + ' ' + DaughterString;
    end;
  end;
  result := MaxRes;
end;

begin
  writeln(Part(100, 3, s):10:1);//first parameter-Enemies count,
                                //2-Number of rounds,
                                //3-output for eliminated enemies counter
  writeln(s);
  readln;
end.

一场有100个对手的比赛，赢尽可能多的钱

A game with 100 oponnents, win as much money as possible

algorithm

math

pascal