Tricky problema de programación que tengo problemas para entender

Question

En primer lugar, déjame decirte que esto no es tarea (soy un estudiante de nivel A, esto no es nada cerca de lo que solucionamos problema (esto es manera) más difícil)), pero estoy tratando de descubrir más de un problema para mejorar mi lógica de programación.

Pensé en un escenario donde hay una matriz de enteros aleatorios, digamos por ejemplo 10 enteros. El usuario ingresará un número con el que quiere contar, y el algoritmo intentará calcular qué números se necesitan para hacer esa suma. Por ejemplo, si quiero hacer la suma 44 de esta matriz de enteros:

myIntegers = array(1, 5, 9, 3, 7, 12, 36, 22, 19, 63); 

La salida sería:

36 + 3 + 5 = 44 

O algo por el estilo. Espero ser claro. Como una ventaja adicional, me gustaría hacer que el algoritmo elija la menor cantidad de números posible para hacer la suma requerida, o dar un error si la suma no se puede hacer con los números suministrados.

Pensé en usar recursividad y iterar a través de la matriz, agregando números una y otra vez hasta que la suma se cumple o se pasa. Pero lo que no puedo entender es qué hacer si el algoritmo va más allá de la suma y debe ser selectivo sobre qué números elegir de la matriz.

No estoy buscando un código completo, o un algoritmo completo, solo quiero su opinión sobre cómo debo proceder con esto y tal vez compartir algunos consejos o algo. Probablemente empiece a trabajar en esto esta noche. : P

Como dije, no deberes. Solo quiero hacer algo un poco más avanzado.

Gracias por cualquier ayuda que pueda ofrecer. :)

Answer 1

Usted está buscando en la Knapsack Problem

El problema de la mochila o un problema de la mochila es un problema en la optimización combinatoria: Dado un conjunto de elementos, cada uno con un peso y un valor, determinar el número de cada elemento para incluir en una colección para que el peso total sea menor que un límite dado y el valor total sea lo más grande posible. Debe su nombre al problema que enfrenta alguien que está limitado por una mochila de tamaño fijo y debe llenarlo con los artículos más útiles.

---

Editar: Su caso especial es el Subset Sum Problem

Answer 2

Will subset sum do? ;]

Answer 3

No sé exactamente lo que es esta tarea se llama, pero parece que es una especie de http://en.wikipedia.org/wiki/Knapsack_problem.

Answer 4

Este es el problema clásico Knapsack que vería en el curso de algoritmos de nivel universitario (o al menos lo vi entonces). Lo mejor es resolverlo en papel y la solución en código debería ser relativamente fácil de resolver.

EDITAR: Una cosa a considerar es dynamic programming.

Answer 5

Tu problema está relacionado con subset sum problem. Tienes que probar todas las combinaciones posibles en el peor de los casos.

Answer 6

No hay atajos aquí, me temo. Además de lo que otras personas han dicho, acerca de qué problema específico es esto, aquí hay algunos consejos prácticos para ofrecerle un punto de partida:

Me gustaría ordenar la matriz y dado el valor de entrada m, encontraría el primer número en el conjunto de menos de m, llámelo n (este es su primer número posible para la suma), y comience desde el complemento más alto posible (m-n), trabajando hacia abajo.

Si no encuentra una coincidencia exacta, escoger el más alto disponible, lo llaman o, (que ahora es su segundo número) y buscar la tercera uno a partir de ( m-n-o) y su forma de trabajo de nuevo.

Si no encuentra una coincidencia exacta, comience con el siguiente número n (índice de n original en el índice-1) y haga lo mismo. Puedes seguir haciendo esto hasta que encuentres una coincidencia precisa para dos números. Si no se encuentra ninguna coincidencia para la suma de dos números, comience nuevamente el proceso, pero amplíelo para incluir un tercer número. Y así.

Eso podría hacerse recursivamente. Al menos este enfoque asegura que cuando encuentre una coincidencia, será la que tenga el menor número posible en el conjunto que forma la suma total de entrada.

Potencialmente, en el peor de los casos, terminas pasando por todo el lote.

Editar: Como Venr señala correctamente, mi primer enfoque fue incorrecto. Enfoque editado para reflejar esto.

Answer 7

Heh, jugaré la tarjeta de "especificación incompleta" (¡nadie dijo que los números no podrían aparecer más de una vez!) Y reduzco esto al problema de "hacer cambios". Ordene sus números en orden decreciente, encuentre el primero menos que su suma deseada, luego reste eso de su suma (la división y los residuos podrían acelerar esto). Repita hasta que sum = 0 o no se encuentre un número menor que la suma.

Para completar, necesitaría hacer un seguimiento de la cantidad de sumandos en cada suma, y ​​por supuesto generar las secuencias adicionales haciendo un seguimiento del primer número que usa, salteándolo y repitiendo el proceso con los números adicionales . Esto resolvería el problema (7 + 2 + 1) sobre (6 + 4).

Answer 8

Hay un algoritmo aleatorizado muy eficiente para este problema. Sé que ya aceptaste una respuesta, pero me complace compartirla de todos modos, solo espero que la gente todavía verifique esta pregunta :).

Let Used = list of numbers that you sum. 
Let Unused = list of numbers that you DON'T sum. 
Let tmpsum = 0. 
Let S = desired sum you want to reach. 

for (each number x you read) 
    toss a coin: 
    if it's heads and tmpsum < S 
     add x to Used 
    else 
     add x to Unused 

while (tmpsum != S) 
    if tmpsum < S 
    MOVE one random number from Unused to Used 
    else 
    MOVE one random number from Used to Unused 

print the Used list, containing the numbers you need to add to get S 

Esto será mucho más rápido que la solución de programación dinámica, especialmente para las entradas aleatorias. Los únicos problemas son que no puede detectar de manera confiable cuando no hay solución (puede dejar que el algoritmo se ejecute durante unos segundos y, si no termina, asumir que no hay solución) y que no puede estar seguro de que obtendrá la solución con el mínimo número de elementos elegidos. De nuevo, podría agregar algo de lógica para hacer que el algoritmo continúe e intente encontrar una solución con menos elementos hasta que se cumplan ciertas condiciones de detención, pero esto lo hará más lento. Sin embargo, si solo está interesado en una solución que funciona y tiene MUCHOS números y la suma deseada puede ser MUY grande, probablemente sea mejor que el algoritmo DP.

Otra ventaja de este enfoque es que también funcionará para números negativos y racionales sin modificaciones, lo que no es cierto para la solución DP, porque la solución DP implica el uso de sumas parciales como índices de matriz, y los índices solo pueden ser números naturales.Por supuesto, puede usar hashtables, pero eso hará que la solución DP sea aún más lenta.

Answer 9

Repitiendo la respuesta de los demás: es un problema de suma de subconjuntos. Podría resolverse de manera eficiente mediante la técnica de programación dinámica.

No se ha mencionado aún lo siguiente: el problema es Pseudo-P (o NP-Completo en sentido débil).

La existencia de un algoritmo (basado en la programación dinámica) polinomial en S (donde S es la suma) yn (el número de elementos) demuestra esta afirmación.

Atentamente.

Answer 10

Ok, escribí un programa C++ para resolver el problema anterior. El algoritmo es simple :-)

Primero organice cualquier matriz que tenga en orden descendente (he codificado la matriz en forma descendente, pero puede aplicar cualquiera de los algoritmos de clasificación).

Siguiente Tomé tres pilas n, pos y sum. El primero almacena el número para el cual se puede encontrar una posible combinación de suma, el segundo contiene el índice de la matriz desde donde comienza la búsqueda, el tercero almacena los elementos cuya adición le dará el número que ingrese.

La función busca el número más grande en la matriz que sea menor o igual al número ingresado. Si es igual, simplemente empuja el número en la pila de suma. De lo contrario, empuja el elemento de matriz encontrado a la pila de suma (temporalmente), y encuentra la diferencia entre el número que busca y el número encontrado, y luego realiza la recursión.

Déjame mostrarte un ejemplo: - para encontrar 44 en 63,36,22,19,12,9,7,5,3,1 {}

primeros 36 serán empujados en suma (más grande número menor que 44) 44-36 = 8 será empujado en n 8-7 = 1 será empujado en n 7 será empujado en suma (número siguiente para buscar) 1 será empujado en suma

así 44 = 36 + 7 + 1 :-)

#include <iostream> 
#include<conio.h> 
using namespace std; 

int found=0; 
void func(int n[],int pos[],int sum[],int arr[],int &topN,int &topP,int &topS) 
{ 
int i=pos[topP],temp; 
while(i<=9) 
{ 
    if(arr[i]<=n[topN]) 
    { 
     pos[topP]=i; 
     topS++; 
     sum[topS]=arr[i]; 
     temp=n[topN]-arr[i]; 
     if(temp==0) 
      { 
       found=1; 
       break; 
     } 
topN++; 
     n[topN]=temp; 
     temp=pos[topP]+1; 
     topP++; 
     pos[topP]=temp; 
     break; 
    } 
    i++; 
} 
if(i==10) 
{ 
    topP=topP-1; 
    topN=topN-1; 
    pos[topP]+=1; 
    topS=topS-1; 
    if(topP!=-1) 
    func(n,pos,sum,arr,topN,topP,topS); 
} 
else if(found!=1) 
func(n,pos,sum,arr,topN,topP,topS); 
} 

main() 
{ 
int x,n[100],pos[100],sum[100],arr[10]={63,36,22,19,12,9,7,5,3,1},topN=-1,topP=-1,topS=-1; 
cout<<"Enter a number: "; 
cin>>x; 
topN=topN+1; 
n[topN]=x; 
topP=topP+1; 
pos[topP]=0; 
func(n,pos,sum,arr,topN,topP,topS); 
if(found==0) 
    cout<<"Not found any combination"; 
else{ 
cout<<"\n"<<sum[0]; 
for(int i=1;i<=topS;i++) 
    cout<<" + "<<sum[i]; 
} 
getch(); 
} 

Puede copiar el código y pegarlo en su IDE, funciona bien :-)