Perché l'algoritmo goloso è ottimale?

Question

Codilità, lezione 14, task TieRopes (https://codility.com/demo/take-sample-test/tie_ropes). In breve, il problema è di partizionare una lista di interi positivi A nel numero massimo di sottolisti (contigui) con somma almeno K.

Ho appena trovato una soluzione avida perché è il nome della lezione. Supera tutti i test ma non so perché sia ​​una soluzione ottimale (se è ottimale).

int solution(int K, vector<int> &A) { 
    int sum = 0, count = 0; 
    for (int a : A) 
    { 
     sum += a; 
     if (sum >= K) 
     { 
      ++count; 
      sum = 0; 
     } 
    } 
    return count; 
} 

Qualcuno può dirmi se e perché questa soluzione è ottimale?

Answer 1

Forse sono ingenuo o sto facendo qualche errore qui, ma penso che non sia troppo difficile (anche se non ovvio) per vedere che l'algoritmo è davvero ottimale.

Supponiamo di avere una partizione ottimale della lista con il numero massimo di sottoliste. Puoi avere o meno tutti gli elementi della lista, ma dal momento che aggiungere un elemento a un elenco valido produce anche un elenco valido, supponiamo che qualsiasi possibile elemento "rimanente" che inizialmente non era assegnato a nessun sottolista fosse assegnato arbitrariamente a uno dei suoi sottolisti adiacenti; quindi abbiamo una partizione ottimale corretta della lista, che chiameremo P1.

Ora pensiamo alla partizione che l'algoritmo vorrebbe produrre, per esempio P2. Ci sono due cose che possono accadere per la prima sottolista in P2:

1. Può essere uguale alla prima sottolista in P1.
2. Può essere più breve della prima sottolista in P1.

In 1. si ripeterà il ragionamento a partire dall'elemento successivo dopo la prima sottolista. Se ogni successiva sottolista prodotta dall'algoritmo è uguale a quella in P1, allora P1 e P2 saranno uguali.

In 2. si ripeterà anche il ragionamento, ma ora è disponibile almeno un elemento "extra". Quindi, di nuovo, la prossima sottolista potrebbe:

2.1. Vai fino alla prossima sottolista in P1.
2.2. Termina prima della successiva sottolista in P1.

E ripetere. Quindi, in ogni caso, avrai almeno come molti sottolisti come P1. Il che significa che P2 è almeno valido come qualsiasi partizione dell'elenco e, in particolare, qualsiasi partizione ottimale.

Non è una dimostrazione molto formale, ma I è valido. Per favore, fai notare tutto ciò che pensi possa essere sbagliato.

Answer 2

Ecco le idee che portano a una dimostrazione formale.

1. Se A è un suffisso di B, allora la dimensione massima della partizione per A è inferiore o uguale alla dimensione massima partizione per B, perché possiamo estendere il primo elenco secondario di una partizione di A per includere il nuovi elementi senza diminuire la sua somma.

2. Ogni prefisso corretto di ogni sottolista nella soluzione golosa corrisponde a meno di K.

3. Non c'è motivo di avere spazi vuoti, perché possiamo aggiungere gli elementi mancanti ad una lista adiacente (ho pensato che la mia formulazione della domanda avesse escluso questa possibilità per definizione, ma lo dirò comunque).

La prova convenzionale può essere effettuata per induzione per dimostrare che, per ogni intero non negativo i, esiste una soluzione ottimale che concorda con la soluzione avido sui primi i sottoliste di ciascuno. Ne consegue che, quando i è sufficientemente grande, l'unica soluzione che è d'accordo con l'avidità è avida, quindi la soluzione golosa è ottimale.

La base i = 0 è banale, poiché una soluzione ottimale arbitraria farà. Il passo induttivo consiste nel trovare una soluzione ottimale che sia d'accordo con le avide sulle prime sottoliste i e poi ridurre la sottolista i+1 in modo che corrisponda alla soluzione avida (dall'osservazione 2, stiamo davvero riducendo quella sottolista, poiché inizia nella stessa posizione di avidi: con l'osservazione 1, possiamo estendere la sottolista i+2 della soluzione ottimale corrispondentemente).