Dato un numero X, come trovo da una matrice di numeri, una combinazione unica che somma fino a X e ha la somma dei quadrati più bassa?

Question

Dato un numero X, come trovo da una matrice di numeri, una combinazione unica che somma fino a X e ha la somma dei quadrati più bassa?

#1 da (2 voti)
#2 da (1 voti)

1

Dato il numero 15 e l'array [1, 2, 3, 4, 5, 6]

Le possibili combinazioni (somma = 15) sarebbero:
[1, 2, 3, 4, 5]
[2, 3, 4, 6]
[1, 3, 5, 6]
[4, 5, 6]

La loro rispettiva somma di quadrati sarebbe:
55, 65, 71 e 77

Qualsiasi numero nell'array può essere utilizzato una sola volta in una qualsiasi combinazione di numeri (nessun numero ripetuto). La soluzione sarebbe la combinazione numerica con la più piccola somma di quadrati (cioè 55)

Quale potrebbe essere una logica efficiente per risolvere questo problema?

Finora, ho provato questo:

Nested for loops:

for (j=0; j<arrLength; j++){
    sum = 0;
    for (i=j; i<arrLength; i++){
        sum+=arrNumbers[i];
        if (sum >= 15) {break;}
    }
}
if (sum == 15) {
    for(j=j; j<=i; j++){
    printf("%d ", arrNumbers[j]);
}

Tuttavia, questo non sempre dà i risultati corretti perché controlla solo le combinazioni di numeri in successione (ad esempio [1, 2, 3], [2, 3, 4], [3, 4, 5])

Dopo ho provato questo:

for (j=0; j<arrLength; j++){
    sum = 0;
    for (k=j; k<arrLength; k++){
        if (sum == 15) {break;}
        sum=arrNumbers[j];
        for (i=k+1; i<arrLength; i++){
            sum+=arrNumbers[i];
            if (sum >= 15) {break;}
        }
    }
    if (sum >= 15) {break;}
}
if(sum==15){
    //print number combinations here
}

Non ha funzionato neanche come ho appreso in seguito che non è molto diverso dalla prima soluzione e la mia logica è imperfetta.

Ciò di cui sto avendo problemi è il tentativo di pensare a una logica che itera attraverso tutti i numeri nell'array (indipendentemente dall'ordine) per trovare combinazioni che si sommano al numero 15.

Ad esempio, il mio codice può trovare queste combinazioni se sono in ordine sequenziale [1, 2, 3, 4, 5] o [4, 5, 6] ma non riesce a trovare qualcosa come [1, 3, 5, 6] .

c programming-logic

posta Vinayak 18.09.2014 - 05:50

fonte

2 risposte

1

What could be an efficient logic to solve this problem?

Non ce ne sono. Anche la prima parte della tua domanda, "Dato un numero X, trova un sottoinsieme che le sommi", è NP-Complete. Se si riuscisse a trovare un algoritmo efficiente per risolvere questo problema, si sarebbe in fila per un premio Nobel.

risposta data 18.09.2014 - 11:28

fonte

Leggi altre domande sui tag c programming-logic

Diritti di amministratore per un set di codice Tipizzazione statica e battitura dinamica [chiusa]

score 2 · Accepted Answer

Un possibile approccio consiste nel generare tutte combinazioni (o sottoinsiemi) dell'array (google per "generare combinazioni c" o "generare sottoinsiemi c" e troverai molti esempi).

Quindi aggiungi gli elementi di ciascuna combinazione, controlla se la somma è uguale a 15 e, se ciò è vero, mantieni la combinazione per il test "somma dei quadrati più bassi".

Lo svantaggio di questo approccio è che se si tenta di elaborare array più grandi, diventa molto lento. Per una matrice di dimensione n, ci sono 2 ^ n combinazioni possibili. Per n = 6, questo è ok, per n = 100, dovrai aspettare per sempre.

Quindi, se stai cercando un algoritmo più efficiente, ti suggerisco di provare un approccio ricorsivo. I sottoinsiemi di un insieme di elementi a1,...a_n possono essere divisi in quelli contenenti a_n e quelli che non contengono a_n . Pertanto i sottoinsiemi con una somma specifica s sono formati da

i sottoinsiemi di a1,...a_(n-1) riassumendo fino a s
i sottoinsiemi di a1,...a_(n-1) riassumendo fino a s - a_n , combinati con l'elemento a_n

Questo processo ricorsivo può essere fermato quando s diventa 0 o negativo, o la somma totale degli elementi a1,...a_k rimanenti diventa inferiore a s , o quando s è maggiore 0, ma l'elemento più piccolo a_1 è maggiore di s.

Mi aspetto che questo approccio ricorsivo sia molto più veloce per gli array più grandi.