Problema del algoritmo VB, encontrar un número específico de una pila de números

Este es un problema de suma de subconjuntos. Es un problema NP bien conocido en la teoría de algoritmos.

Existen varias soluciones clásicas:

1. Hay combinaciones de todos los elementos del conjunto, luego se suman y se comparan con el objetivo de suma. El método es simple, pero la complejidad del algoritmo es alta. Cuando el número de conjuntos es grande, como ≥ 15, la velocidad es obviamente lenta;

2. La solución recursiva es un esquema típico de divide y vencerás.

3. Retroceder, la subcolección es un caso especial de esto. -- Aunque también requiere recursividad, en comparación con el método anterior, puede mantener una buena eficiencia cuando la colección es relativamente grande.

El código VB para el método de retroceso se proporciona a continuación (VB 2010).

?Privado?Sub?salida(ByRef?ta()?As?Integer, ?ByVal?ta_size?As?Integer)

Dim?ra(ta_size?-?1)?As?Integer?'differ ?from?c/c

Array.Copy(ta,?ra,?ta_size)

Dim?converter?=?New?Converter(Of?Integer,?String)( Function(num)?num.ToString)

Dim?str?=?String.Join(" ",?Array.ConvertAll(ra,?converter))

lbSubset.Items .Add(str) End?Sub

Privado?Sub?getSubsetSum(ByRef?sa()?As?Integer, ?ByRef?ta()?As?Integer, ByVal?sa_size?As?Integer, ?ByVal?ta_size?As?Integer, ByVal?sum?As?Integer, ?ByVal?cnt_node?As?Integer, ?ByVal?target?As?Integer)

Dim?i?As?Integer

Si?objetivo?=?suma?Entonces

salida(ta,?ta_size)

Si?cnt_node?1?lt; suma?-?sa(cnt_node)? ?sa(cnt_node? ?1)?lt;=?target?Entonces

getSubsetSum(sa,?ta,?sa_size,?ta_size?-?1,? suma?-?sa(cnt_node),?cnt_node? ?1,?target)

Fin?Si

Regresar

Else

Si?cnt_node?lt;?sa_size?Y?sum? ?sa(cnt_node)?lt;=?target?Entonces

Para?i?=?cnt_node?To?sa_size?-?1? '?difier?de?c/c

ta(ta_size)?=?sa(i)

Si?sum?sa(i)?lt;=?target? Luego

getSubsetSum(sa, ?ta, ?sa_size, ?ta_size? ?1, ?sum? ?sa(i), ?i? ?1, ?target)

Fin ?Si

Siguiente?i

Fin?Si

Fin?Si

Fin?Sub

Privado ?Sub?generateSubsets(ByRef?sa()?As?Integer, ?ByVal?size?As?Integer, ?ByVal?target?As?Integer)

Dim?ta(tamaño?-?1) ?As?Integer

Dim?total?As?Integer?=?0

Array.Sort(sa)

total?=?sa.Sum< /

p>

Si?(sa(0)?lt;=?target)?Y?(total?gt;=?target)?Entonces

getSubsetSum(sa,?ta,?size, ?0,?0,?0,?target)

Fin?Si

Fin?Sub Private?Sub?btnStart_Click(remitente?As?System.Object,?e?As ?System.EventArgs)?Handles?btnStart.Click

Dim?size?As?Integer?=?15

Dim?target?As?Integer?=?10

¿Dim?data()?As?Integer

¿Dim?i?As?Integer

lbSubset.Items.Clear()

¿ReDim? data(size?-?1)?'difier?from?c/c

Para?i?=?LBound(data)?To?UBound(data)

data( i)?=?i?1

Siguiente?i

generarSubconjuntos(datos,?tamaño,?objetivo)

Fin?Sub