algorithm - 一场有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

看来这个问题有一个可以提前计算的数学答案。正如@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.