Subset sum problem ili problem sume podskupa definiše se nad skupom cijelih brojeva, iz kojeg je potrebno naći podskup čija suma elemenata iznosi određenu vrijednost.

Problem se može poopćiti na sljedeći jednostavan primjer:

Pretpostavimo da imamo skup . Potrebno je prebrojati koliko ima podskupava datog skupa čiji zbir elemenata iznosi npr. 7.

Prejednostavan problem, čak se i napamet se može izračunati, bez olovke i papira, a implementacija u nekom programskom jeziku je prejednostavna. Međutim, u koliko se radi o skupu koji ima veći broj elemenata, i ako se radi o vrijednosti sume takodjer velikom broju, tada nastupa problem, jer se klasično ne može riješiti. Problem je poznat po imenu Subset-Sum problem ili Problem Sume Podskupa. Ovo je pojednostavljena verzija Knapsack problema.

postoji podskup za koji vrijedi

SUBSET-SUM problem: Pretpostavimo da imamo skup , od članova koji predstavljaju cijele brojeve i cijeli broj.

1. Decision problem (problem odluke) postavlja pitanje da li postoji podskup čija suma članova iznosi .
2. Optimization problem (optimizacijski problem) postavlja pitanje koliko ima podskupova čija suma članova iznosi .

Problem koji smo definisali tretira se kao NP problem. Više o NP može se pogledati na datom linku. Koliko je kompleksan ovaj problem zavisi od N i t, a shodno njima se i implementiraju algoritmi za rješavanje.

Matematička analiza problema

Kako je broj elemenata skupa jednak broju , to možemo zaključiti da ukupan broj svih podskupova koji se mogu definisati iz datog skupa je sljedeći:

Vidimo da su podskupovi skupa , kombinacije bez ponavljanja klasa do . Zbir ovih kombinacija iznosi:

Svaki podskup sadrži elemenata shodno razvoju Binomnog obrazca iz gornjeg izraza.

Kompleksnost problema

Obični postupak rješavanja ovih problema je “brute-force”, koji generira sve kombinacije podskupova, kojih ima , a generirane podskupove sada je potrebno provjeriti da li zadovoljavaju (ne)jednakost, što čini još dodatnih N operacija. S toga ovaj problem ima kompleksnost odnosno vrijeme izvršavanje . Ovo spada u grupu eksponencijalnih vremena izvršavanja. Neki pristupi rješavanja svode kompleksnos na , djeleći skup na dva podskupa.

Algoritam

Za specifične vrijednosti i , problem je moguće svesti na pseudo-polinomalni, koji se rješava dinamičkim programiranjem.

Algoritam dinamičkog programiranja za problem odluke:

Pretpostavimo da imamo polje: . Potrebno je provjeriti da li postoji nepazan podskup čija suma iznosi . Neka je suma negativnih članova polja, a suma pozitivnih članova polja. Definišimo boolovu funkciju na način: “postoji neprazan podskup od   čija suma elemenata iznosi “.

Rješenje problema je vrijednost .

1. , ako je , s toga ove vrijednosti netrebaju da budu čuvane tokom izvršavanja.
2. Formirati polje za čuvanje vrijednosti za .
3. Ova kolekcija se popunjava sljedećom rekurzijom
   1. Inicijalizirati
   2. Postaviti početnu vrijednost funkcije
   3. Za
   4. Postaviti ili ili , za .

Za svaki vrijednost na desnoj strani je poznata, jer je izračunata iz prethodnih iteracija ili zbog ako je .

Algoritam optimizacijskog problema

Optimizacijski problem je sličan gore prezentiranom problemu, samo umjesto definisanja boolove funkcije , definišemo funkciju , koja vraća broj podskupova, čija suma elemenata iznosi .

Rješenje optimizacijskog problema je vrijednost .

Primjena Subset Sum problema

U nekoliko narednih primjera biće demonstrirano korištenje prethodnih definicija i algoritma dinamičkog programiranja:

Problem 1. Koliko se može napraviti podskupova skupa , čija je suma .

Problem je vrlo jednostavan jer želimo vidjeti na koji način algoritam radi. Prvo, rješimo ovaj problem „pješice“ i pogledajmo koliko takvih posdkupova ima. To su:

.

Vidimo da ukupno postoji 4 takva podskupa.Napišimo implementaciju ovog problema shodno gore prezentiranom algoritmu.

static void Main(string[] args)
{
    Console.Title = "Subset Sum Problem...";
    //Inicijalizacija skupa S i vrijednosti t
    int[] S = new int[6] { 1, 2, 3, 4, 5, 6 };
    int t = 7;

    //polje za čuvanje vrijednosti Q(s)
    int[] Q=new int[t+1];
    //Pocetna vrijednost
    Q[0]=1;
    //Iteracija od 0-N
    for (int i = 0; i < S.Length; i++)
    {
        int s=S[i];
        //Iteracija od t-si
        for (int j = t; j >= s; j--)
            Q[j] += Q[j - s];
    }
    Console.WriteLine("Postoji {1} podskupa čija je suma>={0}",t,Q.Sum()-1);
    Console.Read();
}

Izlaz na konzolu je sljedeći:

Linija 18 čini čaroliju kod ove implementacije. Važno je naglasiti da iteracija kod druge petlje mora ići u silaznom smijeru od do . U koliko bi išla u suprotnom smjeru tada bi ova implementacija imala sasvim drugi smisao kojem će biti riječi možda neki drugi put.

Gornjom implementacijom ne samo da smo prebrojali koliko postoji podskupova čija je suma 7, nego smo prebrojali i sve podskupove čija je suma manja ili jednaka 7. Kako smo kazali kroz definiciju algoritma da je vrijednost broj podskupova čija je suma iznosi , to znači da je rješenje za problem , i td. Sve do praznog skupa onosno . Ovim se želi kazati da algoritam rješava problem sume manje ili jednake od .

Console.WriteLine("Postoji {1} podskupa čija je suma>={0}",t,Q.Sum()-1);

Od sume oduzimamo jedinicu jer želimo izbaciti prazan skup odnosno .