problema di programmazione Tricky che sto avendo problemi a ottenere la mia testa intorno

StackOverflow https://stackoverflow.com/questions/2320138

Domanda

Prima di tutto, lasciatemi dire che questo non è lavoro (io sono uno studente di specializzazione post diploma, questo è niente vicino a quello che risolvere problemi (questo è via più difficile)), ma più di un problema che sto cercando di suss fuori per migliorare la mia logica di programmazione.

Ho pensato a uno scenario in cui v'è una serie di numeri interi casuali, diciamo per esempio dicono 10 numeri interi. L'utente inserire un numero che vuole contare fino a, e l'algoritmo cercherà di capire cosa i numeri sono necessari per rendere 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 potrebbe essere: 

36 + 3 + 5 = 44

O qualcosa del genere. Spero Sono stato chiaro. Come bonus aggiuntivo Mi piacerebbe fare l'algoritmo di scegliere il minor numero possibile di fare la somma richiesta, o dare un errore se la somma non può essere fatta con i numeri forniti.

Ho pensato di usare la ricorsione e iterazione attraverso l'array, aggiungendo i numeri più e più volte fino a quando la somma viene raggiunto o superato. Ma quello che non riesco a ottenere la mia testa intorno è cosa fare se l'algoritmo va oltre la somma e ha bisogno di essere selettivi su quali numeri di scegliere dalla matrice.

Io non sto cercando di codice completo, o un algoritmo completo, voglio solo le tue opinioni su come devo procedere con questo e forse condividere alcuni consigli o qualcosa del genere. Io probabilmente iniziare a lavorare su questo stasera. : P

Come ho detto, non i compiti a casa. Basta che mi vogliono fare qualcosa di un po 'più avanzato.

Grazie per qualsiasi aiuto si è in grado di offrire. :)

È stato utile?

Soluzione

Stai guardando il zaino problema

  

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 ogni elemento da includere in una raccolta in modo che il peso totale è di meno di un data limite ed il valore totale è il più grande possibile. Il suo nome deriva dal problema affrontato da qualcuno che è vincolata da uno zaino di dimensioni fisse e deve riempire con i prodotti più utili.

Modifica: Il tuo caso particolare è il sottoinsieme Sum problema

Altri suggerimenti

Questo è il classico zaino problema che si vedrebbe in un college corso algoritmi di livello (o almeno ho visto allora). Meglio lavorare questo fuori su carta e la soluzione in codice dovrebbe essere relativamente facile da lavorare fuori.

EDIT:. Una cosa da considerare è programmazione dinamica

Il problema è legato alla sottoinsieme somma problema . Dovete provare tutte le combinazioni possibili nel caso peggiore.

Non ci sono scorciatoie qui ho paura. In aggiunta a ciò che gli altri hanno detto, su ciò che problema specifico si tratta ecc, ecco alcuni consigli pratici per offrire un punto di partenza:

Vorrei ordinare l'array e data la m somma di ingresso, avrebbe trovato il primo numero nella matrice meno di m, chiamarlo n (questo è il primo numero possibile per la somma), e iniziare dalla più alta complemento possibile ( m-n), lavorando la strada 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 precisa, iniziare con il prossimo numero n (indice di originale n a index-1) e fare lo stesso. È possibile continuare a fare questo finché non si trova una corrispondenza precisa per due numeri. Se non può competere con la somma è trovato per due numeri, avviare il processo di nuovo, ma espanderlo per includere un terzo numero. E così via.

che si potrebbero fare in modo ricorsivo. Almeno questo approccio assicura che quando si trova una corrispondenza, sarà quello con il minor numero di possibili nel set che formano la somma totale in ingresso.

Potenzialmente, però, nel peggiore dei casi, si finisce per passare attraverso l'intera partita.

Modifica : Come Venr giustamente sottolinea, il mio primo approccio è stato corretto. A cura approccio per riflettere questo.

C'è un algoritmo randomizzato molto efficace per questo problema. So che già accettato una risposta, ma sono felice di condividere in ogni caso, spero solo che la gente continuerà 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 rispetto alla soluzione di programmazione dinamica, in particolare per gli ingressi casuali. Gli unici problemi sono che non è possibile rilevare in modo affidabile se non esiste una soluzione (si può lasciare che la corsa algoritmo per alcuni secondi e se non finisce, assume non esiste una soluzione) e che non si può essere sicuri che otterrà la soluzione con il numero minimo di elementi scelti. Anche in questo caso, si potrebbe aggiungere un po 'di logica per rendere l'algoritmo di andare avanti e cercare di trovare una soluzione con meno elementi finché non vengono soddisfatte determinate condizioni di arresto, ma questo renderà più lento. Tuttavia, se siete interessati solo a una soluzione che funziona e hai un sacco di numeri e la somma desiderata può essere molto grande, questo è probabilmente meglio che l'algoritmo di DP.

Un altro vantaggio di questo approccio è che funziona anche per i numeri negativi e razionali senza modifiche, che non è vero per la soluzione DP, perché la soluzione DP comporta l'uso di somme parziali come indici di matrice, e indici può essere naturale numeri. È possibile d'uso naturalmente hashtables per esempio, ma che renderà la soluzione DP ancora più lento.

Non so esattamente che cosa è questa operazione si chiama, ma sembra che è una specie di http: //en.wikipedia.org/wiki/Knapsack_problem .

Eh, giocherò la carta "specificazione incompleta" (nessuno ha detto che i numeri non potrebbero apparire più di una volta!) E ridurre questo al "cambiamento facendo" problema. Ordinare i numeri in ordine decrescente, a trovare il primo meno che il vostro somma desiderata, quindi sottrarre che dal vostro sum (divisione e resti potrebbero accelerare l'operazione). Ripetere l'operazione fino sum = 0 o nessun numero inferiore alla somma viene trovato.

Per completezza, si avrebbe bisogno di tenere traccia del numero di addendi in ogni somma, e, naturalmente, generare sequenze aggiuntive per tenere traccia del primo numero si utilizza, saltando quella, e ripetendo il processo con i numeri aggiuntivi. Questo risolverebbe il problema (7 + 2 + 1) sopra (6 + 4).

Ripetendo la risposta degli altri: si tratta di un problema sottoinsieme Sum. Potrebbe essere efficacemente risolto dalla tecnica dinamica Programmazione.

Il seguente non è stato ancora citato: il problema è Pseudo-P (o NP-completo in senso debole)

.

L'esistenza di un algoritmo (basato sulla programmazione dinamica) polinomio in S (dove S è la somma) e n (il numero di elementi) dimostra questa affermazione.

Saluti.

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

Prima di tutto organizzare qualunque schieramento si dispone in ordine decrescente (ho hard-coded la matrice in forma decrescente, ma è possibile applicare uno qualsiasi degli algoritmi di ordinamento).

Poi ho preso tre pile n, pos e somma. Il primo memorizza il numero per il quale una possibile combinazione somma è da ricercarsi, la seconda contiene l'indice della matrice da cui iniziare la ricerca, la terza memorizza gli elementi la cui aggiunta vi darà il numero immesso.

La funzione cerca il numero più grande nella matrice che è minore o uguale al numero inserito. Se è uguale, spinge semplicemente il numero sulla pila somma. Se no, allora spinge l'elemento di matrice incontrato allo stack sum (temporaneamente), e trova la differenza tra il numero di ricercare e il numero incontrato, e poi esegue ricorsione.

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

prima 36 saranno spinti in sum (maggior 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 a somma

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

E 'possibile copiare il codice e incollarlo nel vostro IDE, funziona bene: -)

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top