Problema di programmazione ingannevole che ho difficoltà a girare la testa

Question

Prima di tutto, lasciami dire che questo non è compito (sono uno studente di livello A, questo non è niente vicino a quello che risolviamo (questo è il modo più difficile)), ma più di un problema sto cercando di scoprire come migliorare la mia logica di programmazione.

Ho pensato a uno scenario in cui è presente una matrice di numeri casuali, diciamo ad esempio 10 numeri interi. L'utente inserirà un numero a cui vuole contare e l'algoritmo proverà a calcolare quali numeri sono necessari per ottenere tale somma. Per esempio, se volevo fare la somma 44 da questo array di interi:

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

Il risultato sarebbe:

36 + 3 + 5 = 44 

O qualcosa del genere. Spero di essere chiaro. Come bonus aggiuntivo, vorrei fare in modo che l'algoritmo scelga il minor numero possibile di numeri per ottenere la somma richiesta o emetta un errore se la somma non può essere fatta con i numeri forniti.

Ho pensato di utilizzare la ricorsione e l'iterazione attraverso l'array, aggiungendo numeri ripetutamente fino a quando la somma non viene soddisfatta o superata. Ma quello che non riesco a capire è cosa fare se l'algoritmo supera la somma e deve essere selettivo su quali numeri scegliere dall'array.

Non sto cercando il codice completo o un algoritmo completo, voglio solo le tue opinioni su come dovrei procedere con questo e forse condividere alcuni suggerimenti o qualcosa del genere. Probabilmente comincerò a lavorare su questo stasera. : P

Come ho detto, non i compiti. Solo io voglio fare qualcosa un po 'più avanzato.

Grazie per l'aiuto che sei in grado di offrire. :)

Answer 1

State guardando la Knapsack Problem

Il problema dello zaino o un problema di zaino è un problema in ottimizzazione combinatoria: Dato un insieme di elementi, ciascuno con un peso e un valore, determinare il numero di ciascuna elemento da includere in una raccolta in modo che il peso totale sia inferiore a un determinato limite e il valore totale sia il più ampio possibile. Deriva il suo nome dal problema affrontato da qualcuno che è costretto da uno zaino di dimensioni fisse e deve riempirlo con gli oggetti più utili.

---

Edit: Il tuo caso particolare è il Subset Sum Problem

Answer 2

fare subset sum fare? ;]

Answer 3

Non so esattamente che cosa è questo compito è chiamato, ma sembra che è una specie di http://en.wikipedia.org/wiki/Knapsack_problem.

Answer 4

Questo è il classico problema Knapsack che si vedrebbe negli algoritmi di livello universitario (o almeno l'ho visto allora). È meglio lavorarlo su carta e la soluzione nel codice dovrebbe essere relativamente facile da elaborare.

MODIFICA: Una cosa da considerare è dynamic programming.

Answer 5

Il problema è correlato allo subset sum problem. Devi provare tutte le possibili combinazioni nel peggiore dei casi.

Answer 6

Non ho scorciatoie qui ho paura. In aggiunta a ciò che altre persone hanno detto, su quale problema specifico si tratta ecc., Ecco alcuni consigli pratici per offrirti un punto di partenza:

Vorrei ordinare l'array e dato la somma di input m, troverei il primo numero nell'array inferiore a , chiamalo n (questo è il tuo primo numero possibile per la somma) e inizia dal complemento più alto possibile (m-n), procedendo verso il basso.

Se non si trova una corrispondenza precisa, scegliere il più alto disponibile, lo chiamano o, (che oggi è il vostro secondo numero) e cercare il terzo uno a partire da ( m-n-o) e il tuo lavoro di nuovo.

Se non si trova una corrispondenza esatta, iniziare con il numero successivo n (indice dell'originale n all'indice-1) e fare lo stesso. Puoi continuare a farlo finché non trovi una corrispondenza precisa per due numeri. Se non viene trovata alcuna corrispondenza per la somma di due numeri, avviare di nuovo il processo, ma espanderlo per includere un terzo numero. E così via.

Questo potrebbe essere fatto in modo ricorsivo. Almeno questo approccio garantisce che quando trovi una corrispondenza, sarà quella con il minor numero possibile nel set che forma la somma totale di input.

Potenzialmente però, nel peggiore dei casi, si finisce per passare attraverso l'intero lotto.

Modifica: Come correttamente sottolineato da Venr, il mio primo approccio non era corretto. Approccio modificato per riflettere questo.

Answer 7

Heh, riproduco la scheda "specifica incompleta" (nessuno ha detto che i numeri non possono apparire più di una volta!) E riducono il problema al "fare cambiamento". Ordina i tuoi numeri in ordine decrescente, trova il primo in meno rispetto alla somma desiderata, quindi sottrai quella dalla somma (divisione e resto potrebbero accelerare). Ripeti fino a somma = 0 o nessun numero inferiore alla somma trovata.

Per completezza, è necessario tenere traccia del numero di addendi in ogni somma e, naturalmente, generare le sequenze aggiuntive tenendo traccia del primo numero utilizzato, saltandolo e ripetendo il processo con i numeri aggiuntivi . Questo risolverebbe il problema (7 + 2 + 1) sopra (6 + 4).

Answer 8

C'è un algoritmo randomizzato molto efficiente per questo problema. So che hai già accettato una risposta, ma sono felice di condividere comunque, spero solo che le persone continuino a controllare questa domanda :).

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 

Questo sarà molto più veloce della soluzione di programmazione dinamica, in particolare per gli ingressi casuali. Gli unici problemi sono che non è possibile rilevare in modo affidabile quando non esiste una soluzione (è possibile consentire l'esecuzione dell'algoritmo per alcuni secondi e, se non si risolve, presupporre che non vi sia alcuna soluzione) e che non si è certi di ottenere la soluzione con il numero minimo di elementi scelti. Ancora una volta, è possibile aggiungere qualche logica per far sì che l'algoritmo continui e cercare di trovare una soluzione con meno elementi fino a quando non vengono soddisfatte determinate condizioni di arresto, ma questo lo renderà più lento. Tuttavia, se sei interessato solo a una soluzione che funziona e hai un sacco di numeri e la somma desiderata può essere MOLTO grande, probabilmente è meglio dell'algoritmo DP.

Un altro vantaggio di questo approccio è che funzionerà anche per numeri negativi e razionali senza modifiche, il che non è vero per la soluzione DP, poiché la soluzione DP prevede l'utilizzo di somme parziali come indici di array e gli indici possono essere solo numeri naturali.Ovviamente è possibile utilizzare hashtables, ad esempio, ma ciò renderà la soluzione DP ancora più lenta.

Answer 9

Ripetere la risposta di altri: si tratta di un problema di Somma sottoinsieme. Potrebbe essere risolto in modo efficiente con la tecnica di programmazione dinamica.

Quanto segue non è stato ancora menzionato: il problema è Pseudo-P (o NP-Completo in senso debole).

Esistenza di un algoritmo (basato sulla programmazione dinamica) polinomiale in S (dove S è la somma) en (il numero di elementi) dimostra questa affermazione.

Saluti.

Answer 10

Ok, ho scritto un programma C++ per risolvere il problema precedente. L'algoritmo è semplice :-)

Prima di tutto, ordina qualsiasi array in ordine decrescente (ho codificato l'array in modo discendente ma puoi applicare uno qualsiasi degli algoritmi di ordinamento).

Successivamente ho preso tre pile n, pos e sum. Il primo memorizza il numero per il quale si può trovare una combinazione di possibili combinazioni, il secondo contiene l'indice dell'array da cui iniziare la ricerca, il terzo memorizza gli elementi la cui aggiunta ti darà il numero inserito.

La funzione cerca il numero più grande dell'array che è minore o uguale al numero inserito. Se è uguale, semplicemente spinge il numero sulla somma della pila. In caso contrario, invia l'elemento dell'array rilevato allo stack somma (temporaneamente) e trova la differenza tra il numero da cercare e il numero rilevato e quindi esegue la ricorsione.

Mi permetta di mostrare un esempio: - per trovare 44 in {} 63,36,22,19,12,9,7,5,3,1

primi 36 saranno spinti a sum (il più grande numero inferiore a 44) 44-36 = 8 saranno spinti n (numero successivo per cercare) 7 saranno spinti in somma 8-7 = 1 saranno spinti n 1 saranno spinti in somma

quindi 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(); 
} 

Puoi copiare il codice e incollarlo nel tuo IDE, funziona bene :-)