MAC324 - Estruturas de Dados para Engenharia

Poli/Elétrica - 1o. Semestre de 1999

Desafio - O Problema de Bob Floyd

São dados inteiros positivos 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:

  1. N = 30 e t = 5
  2. N = 40 e t = 15
  3. N = 50 e t = 30
  4. N = 60 e t = 60

Prêmio

Todos os interessados podem submeter suas soluções (isto é, programas). O autor da melhor solução ou melhores soluções receberá a admiração de todos nós, e também uma bela garrafa de vinho.

Para receber o prêmio vinhesco, a sua solução deve pelo menos resolver os casos N <= 40 em tempo razoável.

Observações


Página principal de MAC324 (Poli - 1o. semestre de 1999).
Página de aulas de MAC324 (Poli - 1o. semestre de 1999).
Netscape-HTML Checked!
Y. Kohayakawa <yoshi@ime.usp.br>

Last modified: Mon Mar 1 02:45:48 EST 1999