Problema de programación difícil de que tengo problemas para ponerme la cabeza

Question

En primer lugar, permítanme decir que esto no es la tarea (soy un estudiante de nivel A, esto no es nada cercano a lo que resolvemos los problemas (esto es camino Harder)), pero más un problema estoy tratando de descubrir para mejorar mi lógica de programación.

Pensé en un escenario en el que hay una serie de enteros aleatorios, por ejemplo, digamos 10 enteros. El usuario ingresará un número al que quiere contar, y el algoritmo intentará resolver qué números se necesitan para hacer esa suma. Por ejemplo, si quería 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 dejarme claro. Como beneficio 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 y iterando a través de la matriz, agregando números una y otra vez hasta que la suma se cumpla o pasó. Pero lo que no puedo entender es qué hacer si el algoritmo pasa la suma y necesita ser selectivo sobre qué números elegir 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 así. Probablemente comenzaré a trabajar en esto esta noche. :PAGS

Como dije, no la tarea. Solo yo queriendo hacer algo un poco más avanzado.

Gracias por cualquier ayuda que pueda ofrecer. :)

Answer 1

Estás mirando el Problema de mochila

El problema de la mochila o el 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, determine 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 es lo más grande posible. Deriva su nombre del 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 Problema de suma del subconjunto

Answer 2

Voluntad suma de subconjunto ¿hacer? ;

Answer 3

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

Editar: una cosa a considerar es programación dinámica.

Answer 4

Tu problema está relacionado con el Problema de suma del subconjunto. Tienes que probar todas las combinaciones posibles en el peor de los casos.

Answer 5

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

Ordenaría la matriz y dada la suma de entrada m, encontraría el primer número en la matriz menos de m, llámalo 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 precisa, elija el más alto disponible, llámelo, llámelo o, (ese ahora es su segundo número) y busque el tercero a partir de (m-n-o) y vuelve a trabajar.

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

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

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

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

Answer 6

Hay un algoritmo aleatorizado muy eficiente para este problema. Sé que ya aceptaste una respuesta, pero estoy feliz de compartir de todos modos, solo espero que la gente todavía revise 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. Los únicos problemas son que no puede detectar de manera confiable cuándo no hay 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 un número mínimo de elementos elegidos. Una vez más, puede agregar algo de lógica para que el algoritmo continúe e intente encontrar una solución con menos elementos hasta que se cumplan ciertas condiciones de parada, pero esto lo hará más lento. Sin embargo, si solo está interesado en una solución que funcione y tiene muchos números y la suma deseada puede ser muy grande, esto 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 usar sumas parciales como índices de matriz, y los índices solo pueden ser números naturales. Por supuesto, puede usar hashtables, por ejemplo, pero eso hará que la solución DP sea aún más lenta.

Answer 7

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

Answer 8

Je, jugaré la tarjeta de "especificación incompleta" (¡nadie dijo que los números no pudieran 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 restos podrían acelerar esto). Repita hasta la suma = 0 o ningún número menos de lo que se encuentra la suma.

Para completar, deberá realizar un seguimiento del número de complementos en cada suma y, por supuesto, generar las secuencias adicionales realizando un seguimiento del primer número que usa, saltando y repitiendo el proceso con los números adicionales. Esto resolvería el problema (7 + 2 + 1) sobre (6 + 4).

Answer 9

Repetir la respuesta de los demás: es un problema de suma de subconjunto. Podría resolverse eficientemente mediante la técnica de programación dinámica.

El siguiente aún no se ha mencionado: el problema es pseudo-P (o NP-complete en sentido débil).

Existencia de un algoritmo (basado en programación dinámica) polinomio en S (donde s es la suma) y N (el número de elementos) demuestra esta afirmación.

Saludos.

Answer 10

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

En primer lugar, 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).

Luego 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 iniciar la búsqueda, la tercera 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 más pequeño o igual al número ingresado. Si es igual, simplemente empuja el número a la pila de suma. Si no, entonces empuja el elemento de matriz encontrado a la pila de suma (temporalmente), y encuentra la diferencia entre el número para buscar y el número encontrado, y luego realiza la recursión.

Permítanme mostrar un ejemplo:- encontrar 44 en {63,36,22,19,12,9,7,5,3,1}

Los primeros 36 se empujarán en suma (número más grande inferior a 44) 44-36 = 8 se empujará en n (el siguiente número para buscar) 7 se empujará en la suma 8-7 = 1 se empujará 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 :-)