N e t.
Considere os números
sqrt(1), sqrt(2), ... , sqrt(N).
O problema de Floyd pede que se ache uma partição deste conjunto de
números em duas partes de forma que as somas dos elementos de cada uma
das partes sejam as mais próximas possíveis. Esta partição deve ser
encontrada usando-se no máximo t segundos de tempo de
computação.
Como um exemplo, para N = 30, idealmente você deveria
encontrar as partes:
sqrt(2)
+ sqrt(6)
+ sqrt(9)
+ sqrt(11)
+ sqrt(12)
+ sqrt(13)
+ sqrt(14)
+ sqrt(21)
+ sqrt(23)
+ sqrt(24)
+ sqrt(25)
+ sqrt(26)
+ sqrt(27)
+ sqrt(30)
=
56.041422588073351...
e
sqrt(1)
+ sqrt(3)
+ sqrt(4)
+ sqrt(5)
+ sqrt(7)
+ sqrt(8)
+ sqrt(10)
+ sqrt(15)
+ sqrt(16)
+ sqrt(17)
+ sqrt(18)
+ sqrt(19)
+ sqrt(20)
+ sqrt(22)
+ sqrt(28)
+ sqrt(29)
=
56.0414226276199557...,
que é a solução ótima para este caso.
Alguns pares (N, t) de interesse:
N = 30 e t = 5
N = 40 e t = 15
N = 50 e t = 30
N = 60 e t = 60
Para receber o prêmio vinhesco, a sua solução deve pelo menos resolver
os casos N <= 40 em tempo razoável.
N = 60 e
t = 60 é interessante, acho, mesmo levando em conta a
literatura já existente.
Y. Kohayakawa
<yoshi@ime.usp.br>
Last modified: Mon Mar 1 02:45:48 EST 1999