Você recebe um conjunto de números inteiros positivos. Você deve organizá-los em pares de modo que:

• Cada par contém 2 números, um dos quais é múltiplo do outro. Por exemplo, 8 é um múltiplo de 4 e 9 é um múltiplo de 9.
• Se o mesmo número ocorrer muitas vezes no conjunto inicial, ele poderá ser usado várias vezes nos pares; um número pode até ser emparelhado com outra ocorrência do mesmo número
• O número máximo possível de pares é obtido.

A saída deve ser o número de pares. O menor código vence.

Dados de amostra

2,3,4,8,9,18 -> 3

7,14,28,42,56 -> 2

7,1,9,9,4,9,9,1,3,9,8,5 -> 6

8,88,888,8888,88888,888888 -> 3

2,6,7,17,16,35,15,9,83,7 -> 2

Haskell, 109 107 76 70 bytes

Obrigado a nimi por salvar 33 bytes e me ensinar um pouco mais de Haskell. :)
Obrigado ao xnor por salvar outros 6 bytes.

import Data.List
f l=maximum$0:[1+f t|a:b:t<-permutations l,a`mod`b<1]

Sim, meu primeiro golfe Haskell. Funciona da mesma forma que todas as respostas até agora (bem, não exatamente: conta apenas o comprimento do prefixo mais longo de pares válidos em cada permutação, mas isso é equivalente e é realmente o que meu código CJam original fez).

Para golfitude extra, também é ineficiente ao gerar recursivamente todas as permutações do sufixo cada vez que os dois primeiros elementos de uma permutação são um par válido.

CJam, 22 18 bytes

q~e!{2/::%0e=}%:e>

Experimente online.

Espera entrada na forma de uma lista no estilo CJam.

Isso é um pouco ineficiente para listas maiores (e o Java provavelmente ficará sem memória a menos que você forneça mais).

Explicação

q~     e# Read and evaluate input.
e!     e# Get all distinct permutations.
{      e# Map this block onto each permutation...
  2/   e#   Split the list into (consecutive) pairs. There may be a single element at the
       e#   end, which doesn't participate in any pair.
  ::%  e#   Fold modulo onto each chunk. If it's a pair, this computes the modulo, which
       e#   yields 0 if the first element is a multiple of the second. If the list has only
       e#   one element, it will simply return that element, which we know is positive.
  0e=  e#   Count the number of zeroes (valid pairs).
}%
:e>    e# Find the maximum of the list by folding max() onto it.

Pitão, 13 bytes

eSm/%Mcd2Z.pQ

A complexidade do tempo e do armazenamento é realmente terrível. A primeira coisa que faço é criar uma lista com todas as permutações da lista original. Isso requer n*n!armazenamento. As listas de entrada com comprimento 9 já demoram bastante tempo.

Experimente on-line: Demonstration or Test Suite

Explicação:

eSm/%Mcd2Z.pQ
            Q   read the list of integer
          .p    create the list of all permutations
  m             map each permutation d to:
      cd2          split d into lists of length 2
    %M             apply modulo to each of this lists
   /     Z         count the zeros (=number of pairs with the first 
                   item divisible by the second)
 S              sort these values
e               and print the last one (=maximum)

Mathematica, 95 93 87 83 79 60 58 bytes

Max[Count[#~Partition~2,{a_,b_}/;a∣b]&/@Permutations@#]&

Leva alguns segundos para os exemplos maiores.

Matlab (120 + 114 = 234)

  function w=t(y,z),w=0;for i=1:size(z,1),w=max(w,1+t([y,z(i,:)],feval(@(d)z(d(:,1)&d(:,2),:),~ismember(z,z(i,:)))));end

a Principal:

  a=input('');h=bsxfun(@mod,a,a');v=[];for i=1:size(h,1) b=find(~h(i,:));v=[v;[(2:nnz(b))*0+i;b(b~=i)]'];end;t([],v)

• a função topper é chamada pela parte principal.

• a entrada está no formato [. . .]

Matlab (365)

  j=@(e,x)['b(:,' num2str(e(x)) ')'];r=@(e,y)arrayfun(@(t)['((mod(' j(e,1) ',' j(e,t) ')==0|mod(' j(e,t) ',' j(e,1) ')==0)&',(y<4)*49,[cell2mat(strcat(r(e(setdiff(2:y,t)),y-2),'|')) '0'],')'],2:y,'UniformOutput',0);a=input('');i=nnz(a);i=i-mod(i,2);q=0;while(~q)b=nchoosek(a,i);q=[cell2mat(strcat((r(1:i,i)),'|')) '0'];q=nnz(b(eval(q(q~=0)),:));i=i-2;end;fix((i+2)/2)

• Aparentemente, isso é mais longo, mas oneliner e executivo, e eu consegui escapar da permsfunção porque leva uma eternidade.

• Esta função leva muitas repetições para ficar bem silenciosa devido a funções anônimas, estou aberto a sugestões aqui :)