Essa variante do problema da soma do subconjunto é mais fácil de resolver?

Question

Eu tenho um problema relacionado ao Problema da soma do subconjunto E estou me perguntando se as diferenças facilitam, ou seja, solucionável em um período de tempo razoável.

Dado um valor v, um tamanho definido L e uma sequência de números [1, n] s, quantos subconjuntos de tamanho L de s soma para menos que v?

Isso é diferente do problema da soma do subconjunto de três maneiras:

1. Eu me importo com quantos subconjuntos são menos do que um determinado valor, não quantos são igual.
2. Os tamanhos dos subconjuntos são fixos.
3. eu me importo quantos Os conjuntos de definem a menos de V, não apenas se existem.

Existe algum algoritmo razoavelmente eficiente para resolver isso?

EDIT: Obviamente, isso pode ser feito em O (N escolha L) usando uma combinação de algoritmo de geração de combinação. O que realmente estou interessado são hacks inteligentes para acelerar significativamente além disso.

Answer 1

(A versão de decisão do) Seu problema ainda está premiado com NP. A idéia é que, se pudéssemos resolver seu problema, então (para cada tamanho de subconjunto, digamos), poderíamos perguntar quantos conjuntos somam menos que V e quantos soma menos de V-1, e a diferença desses dois números iria Diga -nos se há subconjuntos que a soma é exatamente V - portanto, poderíamos resolver o problema da soma do subconjunto. [Esta não é uma prova completa, porque é um Redução de Turing, não a muitas reduções.]

No entanto, existe um simples programaçao dinamica Solução que é executada no tempo O (NLV). [A razão pela qual isso não prova que p = np é que V pode ser exponencial no tamanho da entrada: com n bits, você pode representar valores até 2ⁿ. Mas assumindo que seu V não é exponencial, isso não é um problema.

Deixe num [v] [k] [i] denotar o número de subconjuntos de tamanho-k dos primeiros elementos i que s soma para v. Você pode calculá-los como (para cada i):

    num[0][0][i] = 1
    for v = 1 to V:
        for k = 1 to L:
            num[v][k][i] = num[v][k][i-1] + num[v-S[i]][k-1][i-1]

onde S [i] é o i -ésimo elemento em sua sequência. (Qualquer conjunto de tamanho K que resume para V não use s [i], então é contado em num [v] [k] [i-1], ou usa s [i], o que significa que o resto de O subconjunto possui elementos K-1, usa apenas os primeiros números de I-1 na sequência e somos para vs [i].) Finalmente, contem num [v] [l] [| s |] para cada v menor que V ; Essa é a sua resposta.

Além disso, você pode omitir o terceiro subscrito se fizer isso com cuidado (execute o loop para baixo para cada i, etc.); Eu só o incluí para clareza.

Answer 2

I'm not prepared to present a proof, but that sounds like it might be amenable to a dynamic programming scheme: tabulate the list of subsets of size 2use them to computer subsets of size 3, etc, so that hyou only need to examine a small collection of prospects.

Answer 3

One optimization that comes to mind is this: Order your sequence (if it alerady isn't so). Pick the first L-1 items from the start of it, and then pick the last item such, that it's the largest possible value (the next largest value in the sequence would give a sum too big). Discard the rest of the sequence, because those items can never be a part of a valid subset anyway.

After that I guess it's full search again. But then again there might be other optimiziations possible too.

Answer 4

The dynamic programming solution to the subset sum problem generates a table that contains this answer (ie a boolean table of V by N where V is the max number of elements and N is the max number of items that can be in a set that satisifies the constraints; each boolean being true if <=N elements sum to <=V). So if N * V is not too large for you, an acceptably fast algorithm exists. The subset sum solution is just the highest set element in this table for which the number of elements is <= N/2.

Answer 5

If it's only positive integers, you can do a verification step if you need;

Take the sum of the L-1 smallest integers in the set. If that's a sum X, then n-X must be below the largest element if the problem is supposed to have a solution. Come to think of it, you can eliminate other L this way...

Answer 6

Well, for one thing since you're specifying size=L then even if you can't think of anything clever and just use brute force you'll have (N choose L) separate sums in the worst case, so it's a bit better than n^^L (well, L+1, as you'd then sum each subset).

Answer 7

This sounds like an n choose k category of problem. Generating k-subsets of n is covered in Skiena's Algorithm Design Manual, and the book suggests enumerating relevant subsets in lexicographic order (recursively, for example). Then do your sum and comparison on each subset.

If you have a sorted set, you could presumably prune impossible solutions from the solution space.

Answer 8

Perhaps the dynamic programming formulation is amenamble to a PTAS of FPTAS.