Sumă dintr-o submulțime: programare dinamică C++

Din valorile 2 3 7 8 putem obține suma 9 alegând 2 și 7. Fiecare poziție din vector poate fi aleasă cel mult o dată. Nu cerem o secvență consecutivă și nu putem refolosi arbitrar aceeași valoare de pe aceeași poziție.

Starea spune dacă o sumă este posibilă

Programarea dinamică păstrează răspunsurile pentru sume mai mici. Variabila posibil[x] este 1 dacă suma x poate fi obținută din elementele deja procesate și 0 altfel. Inițial numai suma zero este posibilă, prin selecția goală.

Citim 0≤n≤100, ținta 0≤S≤10000 și n valori întregi între 0 și 10000. Afișăm DA sau NU. Elementele negative sunt excluse, deoarece intervalul stărilor 0..S și tranziția folosită nu le tratează. Pentru S=0, răspunsul este DA inclusiv când n=0.

De ce mergem de la S spre zero

Pentru elementul a[i], suma x devine posibilă dacă x-a[i] era posibilă înaintea acestui element. Parcurgem x descrescător pentru ca starea x-a[i], mai mică atunci când a[i]>0, să nu fi fost încă actualizată în etapa curentă.

Dacă am parcurge crescător, un singur element 3 ar putea crea mai întâi suma 3, apoi suma 6 folosind chiar starea proaspăt creată. Am folosi aceeași poziție de două ori. Ordinea buclei codifică restricția „cel mult o dată”.

Din 2,3,7,8, suma 9 se obține alegând 2 și 7. Parcurgerea descrescătoare a sumelor împiedică reutilizarea aceleiași poziții.Mărește schema ↗

Varianta cu tablou clasic

#include <iostream>
using namespace std;
int main() {
    int n,s; cin >> n >> s;
    int a[100],posibil[10001]={};
    for(int i=0;i<n;++i) cin >> a[i];
    posibil[0]=1;
    for(int i=0;i<n;++i)
        for(int suma=s;suma>=a[i];--suma)
            if(posibil[suma-a[i]]) posibil[suma]=1;
    cout << (posibil[s]?"DA\n":"NU\n");
}

Varianta echivalentă cu std::vector

Păstrăm limitele intrării și aceleași rezultate. Tabloul clasic rezervă capacitatea maximă; vectorul construiește numărul de elemente necesare. Indicii folosiți de algoritm rămân aceiași.

#include <vector>

#include <iostream>
using namespace std;
int main() {
    int n,s; cin >> n >> s;
    vector<int> a(n),posibil(s+1);
    for(int i=0;i<n;++i) cin >> a[i];
    posibil[0]=1;
    for(int i=0;i<n;++i)
        for(int suma=s;suma>=a[i];--suma)
            if(posibil[suma-a[i]]) posibil[suma]=1;
    cout << (posibil[s]?"DA\n":"NU\n");
}

Zerourile și valorile prea mari

Un element zero nu creează sume noi: fiecare stare se referă la ea însăși. Acest lucru este corect pentru o problemă de existență. Dacă am număra câte selecții produc suma, zerourile ar avea un efect diferit și ar trebui analizate explicit.

Când a[i]>S, bucla interioară nu începe. Pentru valori nenegative, acel element nu poate face parte dintr-o selecție cu suma S. În tabloul clasic rezervăm 10001 de stări; utilizăm numai 0..S. Indicii elementelor intrării sunt 0..n-1.

Timpul este O(n·(S+1)), iar memoria stărilor O(S+1), plus intrarea O(n). Dependența de valoarea numerică a țintei explică de ce această soluție nu este potrivită automat când S ajunge la miliarde, chiar dacă n rămâne mic.

Exersează

2 3 7 8 cu S=9 produce DA. Un singur 3 cu S=6 produce NU și verifică direcția buclei. Pentru 0 0, S=0, rezultatul este DA. Pentru 2 3 7, S=6, rezultatul este NU.

Revezi rucsacul 0/1, submulțimile și stările dinamice.

Întrebări frecvente

Ce reprezintă problema sumei unei submulțimi?

Decizi dacă poți obține o sumă alegând unele poziții din vector, fiecare cel mult o dată. Elementele alese nu trebuie să fie consecutive.

De ce parcurg sumele descrescător în varianta 0/1?

Pentru ca elementul curent să nu fie reutilizat printr-o stare actualizată chiar în aceeași etapă. Parcurgerea crescătoare ar permite în unele cazuri folosirea lui repetată.

De ce suma zero este posibilă de la început?

Selecția goală are suma zero. Această stare inițială permite construirea sumelor care folosesc primul element și exprimă explicit convenția problemei.