Neste desafio, você receberá uma lista de pesos separados por vírgula como entrada, como

1,3,4,7,8,11

E você deve gerar a menor quantidade de pesos que puder adicionar a esse conjunto. Por exemplo, a saída para este conjunto seria

1,3,7

Porque você pode representar todos esses pesos com apenas esses três:

1     = 1
3     = 3
1+3   = 4
7     = 7
1+7   = 8
1+3+7 = 11

Pode haver mais de uma solução. Por exemplo, sua solução para a entrada 1,2pode ser 1,1ou 1,2. Contanto que encontre a quantidade mínima de pesos que possa representar o conjunto de entradas, é uma solução válida.

Os pesos não podem ser usados ​​mais de uma vez. Se você precisar usar um duas vezes, deverá produzi-lo duas vezes. Por exemplo, 2,3não é uma solução válida para 2,3,5,7porque você não pode usá-lo 2duas vezes 2+2+3=7.

A entrada é garantida para não ter números duplicados.

Este é o código-golfe, pelo que o código mais curto por contagem de caracteres vence.

O acesso à rede é proibido (por isso não é da sua "inteligentes" wgetsoluções @JohannesKuhn tosse tosse );)

Casos mais simples:

1,5,6,9,10,14,15               => 1,5,9
7,14,15,21,22,29               => 7,14,15
4,5,6,7,9,10,11,12,13,15,16,18 => 4,5,6,7
2,3,5,7                        => 2,2,3 or 2,3,7

E alguns mais complicados:

10,16,19,23,26,27,30,37,41,43,44,46,50,53,57,60,61,64,68,71,77,80,84,87
  => 3,7,16,27,34
20,30,36,50,56,63,66,73,79,86
  => 7,13,23,43
27,35,44,46,51,53,55,60,63,64,68,69,72,77,79,81,86,88,90,95,97,105,106,114,123,132
  => 9,18,26,37,42

Mathematica 80 75

Atualização: Veja na parte inferior uma atualização sobre o último teste desafiador da Maçaneta, adicionado em 5 de novembro

Isso passa quase no último teste. No entanto, ele não tenta usar um dígito mais de uma vez. E procura apenas soluções que são subconjuntos do conjunto de dados maior.

A função gera todos os subconjuntos do conjunto de dados de entrada e testa quais subconjuntos podem ser usados ​​para construir o conjunto completo. Depois que os subconjuntos viáveis ​​são encontrados, ele escolhe os menores conjuntos.

s=Subsets
f@i_:=GatherBy[Select[s@i,Complement[i, Total /@ s@#]=={}&],Length]〚1〛

Testes

f[{1, 3, 4, 7, 8, 11}]

{{1, 3, 7}}

f[{1, 5, 6, 9, 10, 14, 15}]

{{1, 5, 9}}

f[{7, 14, 15, 21, 22, 29}]

{{7, 14, 15}}

f[{4, 5, 6, 7, 9, 10, 11, 12, 13, 15, 16, 18}]

{{4, 5, 6, 7}}

f[{2, 3, 5, 7}]

{{2, 3, 5}, {2, 3, 7}}

Atualizar

Abaixo, fornecerei uma análise inicial que pode ajudar a começar a encontrar uma solução.

Os dados:

data = {10, 16, 19, 23, 26, 27, 30, 37, 41, 43, 44, 46, 50, 53, 57, 60, 61, 64, 68, 71, 77, 80, 84, 87};

Diferentemente da abordagem anterior, queremos considerar, no conjunto de soluções, números que NÃO aparecem no conjunto de dados.

A abordagem utiliza diferenças absolutas entre pares de números no conjunto de dados.

g[d_] := DeleteCases[Reverse@SortBy[Tally[Union[Sort /@ Tuples[d, {2}]] /. {a_, b_} :> Abs[a - b]], Last], {0, _}] 

Vejamos o número de vezes que cada diferença aparece; pegaremos apenas os 8 primeiros casos, começando pela diferença mais comum].

g[data][[1;;8]]

{{7, 14}, {27, 13}, {34, 12}, {3, 11}, {20, 10}, {16, 10}, {4, 10}, {11, 9}}

14 pares diferem por 7; 13 pares diferem por 27, e assim por diante.

Agora vamos testar subconjuntos começando com {difference1}, {difference1, difference2} e assim por diante, até que possamos, esperançosamente, contabilizar todos os elementos originais no conjunto de dados.

h revela os números do conjunto original que não podem ser construídos compondo somas do subconjunto.

h[t_] := Complement[data, Total /@ Subsets@t]

Na quinta tentativa, ainda existem 10 elementos que não podem ser formados a partir de {7, 27, 34, 3, 20}:

h[{7, 27, 34, 3, 20}]

{16, 19, 26, 43, 46, 53, 60, 77, 80, 87}

Mas na próxima tentativa, todos os números do conjunto de dados são contabilizados:

h[{7, 27, 34, 3, 20, 16}]

{}

Isso ainda não é tão econômico quanto {3,7,16,27,34}, mas está próximo.

Ainda há algumas coisas adicionais a serem consideradas.

1. Se 1 estiver no conjunto de dados, será necessário no conjunto de soluções.
2. Pode haver alguns "solitários" no conjunto original que não possam ser compostos a partir das diferenças mais comuns. Eles precisariam ser incluídos além dos testes de diferença.

Esses são mais problemas do que eu posso lidar no momento. Mas espero que ajude a esclarecer esse desafio muito interessante.

Ruby 289

Como é uma enumeração direta, obterá soluções mínimas, mas poderá levar anos - possivelmente anos-luz - para resolver alguns problemas. Todos os "casos mais simples" são resolvidos em no máximo alguns segundos (embora eu tenha recebido 7,8,14 e 1,2,4 no terceiro e no quinto casos, respectivamente). O complicado número 2 foi resolvido em cerca de 3 horas, mas os outros dois são grandes demais para enumeração, pelo menos pela maneira como eu fiz isso.

Uma matriz de tamanho nque gera a matriz especificada somando subconjuntos de seus elementos é de tamanho mínimo se for possível mostrar que não existe uma matriz de tamanho < nque faça isso. Não vejo outra maneira de provar a otimização; portanto, inicio a enumeração com subconjuntos de tamanho m, onde mhá um limite inferior conhecido, e aumento o tamanho para m+1depois de ter enumerado subconjuntos de tamanho me mostrado que nenhum deles "abrange" o dado matriz, e assim por diante, até encontrar um ótimo. Obviamente, se eu enumerar todos os subconjuntos até o tamanho n, poderia usar uma heurística para o tamanho n + 1, de modo que, se encontrasse uma matriz de abrangência desse tamanho, saberia que é o ideal. Alguém pode sugerir uma maneira alternativa de provar que uma solução é ideal no caso geral?

Incluí algumas verificações opcionais para eliminar algumas combinações desde o início. A remoção dessas verificações salvaria 87 caracteres. Eles são os seguintes ( aé a matriz fornecida):

• uma matriz de tamanho npode gerar no máximo 2^n-1números positivos distintos; portanto,, 2^n-1 >= a.sizeou n >= log2(a.size).ceil(o "limite inferior" a que me referi acima).
• um candidato que gere uma matriz bde tamanho npode ser descartado se:
  • b.min > a.min
  • sum of elements of b < a.max ou
  • b.max < v, onde v = a.max.to_f/n+(n-1).to_f/2.ceil( to_fsendo a conversão para flutuar).

O último deles, verificado primeiro, implementa

sum of elements of b <= sum(b.max-n+1..b.max) < a.max

A nota vé constante para todas as matrizes de tamanho de gerador n.

Também usei a observação muito útil de @card_box de que não há necessidade de considerar duplicatas na matriz geradora.

No meu código,

(1..a.max).to_a.combination(n) 

gera todas as combinações dos números de 1 a a.max, tirados de ncada vez (onde a.max = a.last = a[-1]). Para cada combinação b:

(1...2**n).each{|j|h[b.zip(j.to_s(2).rjust(n,?0).split('')).reduce(0){|t,(u,v)|t+(v==?1?u:0)}]=0}

preenche um hash hcom todos os números somados em subconjuntos não vazios de b. As chaves de hash são esses números; os valores são arbitrários. (Optei por definir o último como zero.)

a.all?{|e|h[e]}}

verifica se cada elemento da matriz fornecida aé uma chave no hash ( h[e] != nil, ou apenas h[e]).

Suponha

n = 3 and b=[2,5,7].

Depois, iteramos no intervalo:

(1...2**8) = (1...8) # 1,2,..,7

A representação binária de cada número nesse intervalo é usada para apurar os elementos de bsoma. Para j = 3( jsendo o índice do intervalo),

3.to_s(2)                  # =>  "11"
"11".rjust(3,?0)           # => "011"
"011".split('')            # => ["0","1","1"]
[2,5,7].zip(["1","0","1"]) # => [[2,"0"],[5,"1"],[7,"1"]]
[[2,"0"],[5,"1"],[7,"1"]].reduce(0){|t,(u,v)|t+(v==?1?u:0)}]=0 # => t = 0+5+7 = 12 

O código:

x=a[-1]
n=Math.log2(a.size).ceil
loop do
v=(1.0*x/n+(n-1)/2.0).ceil
(1..x).to_a.combination(n).each{|b|
next if b[-1]<v||b[0]>a[0]||b.reduce(&:+)<x
h={}
(1...2**n).each{|j|h[b.zip(j.to_s(2).rjust(n,?0).split('')).reduce(0){|t,(u,v)|t+(v==?1?u:0)}]=0}
(p b;exit)if a.all?{|e|h[e]}}
n+=1
end