problems algorithm math numbers np-complete

algorithm - np complete problems list



Problema de programación difícil que me cuesta trabajo. (10)

En primer lugar, permítanme decir que esto no es tarea (soy un estudiante de nivel A, esto no es nada parecido a lo que resolvemos los problemas (esto es mucho más difícil)), sino más bien un problema que estoy tratando de investigar. Mejorar mi lógica de programación.

Pensé en un escenario donde hay una matriz de enteros aleatorios, por ejemplo, digamos 10 enteros. El usuario ingresará un número que desea contar y el algoritmo intentará averiguar qué números se necesitan para hacer esa suma. Por ejemplo, si quisiera 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 aclararme. Como un bono adicional, me gustaría hacer que el algoritmo seleccione 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 la recursión e iterar a través de la matriz, agregando números una y otra vez hasta que la suma se haya cumplido o pasado. Pero lo que no puedo entender es qué hacer si el algoritmo supera la suma y debe ser selectivo sobre qué números seleccionar de la matriz.

No estoy buscando un código completo o un algoritmo completo, solo quiero sus opiniones sobre cómo debo proceder con esto y tal vez compartir algunos consejos o algo. Probablemente empezaré a trabajar en esto esta noche. :PAG

Como he dicho, no es tarea. Solo yo queriendo hacer algo un poco más avanzado.

Gracias por cualquier ayuda que puedas ofrecer. :)

Estás mirando el problema de la mochila

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

Edit: Su caso especial es el en.wikipedia.org/wiki/Subset_sum_problem

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

EDIT: Una cosa a considerar es la programación dinámica .

Hay un algoritmo aleatorio muy eficiente para este problema. Sé que ya aceptaste una respuesta, pero me alegra compartirla de todos modos, solo espero que la gente siga revisando 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 entradas aleatorias. El único problema es que no puede detectar de manera confiable cuando no hay una solución (puede dejar que el algoritmo se ejecute durante unos segundos y, si no termina, suponga que no hay solución) y que no puede estar seguro de que obtendrá la solución Con mínimo número de elementos elegidos. Nuevamente, podría agregar algo de lógica para hacer que el algoritmo continúe y tratar de 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, esto es probablemente mejor que el algoritmo DP.

Otra ventaja de este enfoque es que también funcionará con 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 utilizar tablas hash, por ejemplo, pero eso hará que la solución DP sea aún más lenta.

Heh, jugaré la tarjeta de "especificación incompleta" (¡nadie dijo que los números no podían aparecer más de una vez!) Y reduciría 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 suma = 0 o ningún número menor que la suma encontrada.

Para estar completo, necesitaría realizar 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, omitiendo eso y repitiendo el proceso con los números adicionales. Esto resolvería el problema (7 + 2 + 1) sobre (6 + 4).

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

Yo ordenaría la matriz y dada la suma de entrada m , encontraría el primer número en la matriz menor que m , lo llamaría n (este es su primer número posible para la suma), y comenzaría desde el complemento más alto posible ( mn ), trabajando su camino hacia abajo.

Si no encuentra una coincidencia precisa, elija la más alta disponible, llámela o , (ahora es su segundo número) y busque el tercero que comienza en ( mno ) y mno hacia abajo.

Si no encuentra una coincidencia precisa, comience con el siguiente número n (índice del 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 encuentran coincidencias para la suma de dos números, inicie el proceso nuevamente, pero expándalo para incluir un tercer número. Y así.

Eso se podría hacer recursivamente. Al menos este enfoque garantiza que cuando encuentre una coincidencia, será el que tenga los números menos posibles en el conjunto que forma la suma de entrada total.

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

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

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

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

A continuación tomé tres pilas n, pos y suma. El primero almacena el número para el cual se encuentra una posible combinación de suma, el segundo contiene el índice de la matriz desde donde comenzar la búsqueda, el tercero almacena los elementos cuya adición le dará el número que ingresa.

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

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

los primeros 36 serán empujados en suma (el número más grande menor que 44) 44-36 = 8 serán empujados en n (el siguiente número para buscar) 7 serán empujados en la suma 8-7 = 1 será empujado en n 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 :-)

Repetir la respuesta de otros: es un problema de suma de subconjuntos. Se podría resolver de manera eficiente mediante la técnica de Programación Dinámica.

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

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

Saludos.