subota, 15. prosinca 2012.

Pripreme za algoritme(8)

Pozdrav, danas ćemo se još malo pozabaviti sa dinamičkim programiranjem. Dinamičko programiranje ima puno primjera u programiranju tako da je jako opsežno pa će u našim pripremama zauzeti malo veće mjesto od ostalih. Da se malo posjetimo dinamičko programiranje je programiranje sa nekim spremanjima , to ćemo sada na početku govoriti kako bi nas svatko mogao shvatiti.
 Danas ćemo gledati kombinacije. Imamo N novčanica i pitanje je koliko različitih svota možemo platiti blagajnici od 1 do beskonačno. Kako imamo spremanje imamo polje dp[]. Ja ga uvijek zovem dp kako bi se znalo da radim dinamičko programiranje. Ali, kako ćemo i što spremati? To je uvijek pitanje.
U ovom slučaju nam je najbolje imati u polju true ili false kao može li se svota od M kuna platiti onda dp[m]=true,ako ne onda false. Svotu od 0 kuna možemo napraviti tako da je dp[0]=true; Pa da vidimo kako nam to izgleda u kodu:
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
using namespace std;
int a,b,c,d,e,f;
int dp[1000000];
int niz[1000];
int main()
{
    scanf("%d",&a);
    d=0;
    for(int z=0;z<a;++z)
    {
            scanf("%d",&niz[z]);
            d=d+niz[z];
    }
    //d=d;
    sort(niz,niz+a);
    dp[0]=1;
    for(int z=0;z<a;++z)
    {
           
            for(int j=d;j>=0;--j)
            {
                    if(dp[j]==1 && j+niz[z]<=d)dp[j+niz[z]]=1;
            }
    }
    f=0;
    for(int z=1;z<=d;++z)
    if(dp[z]==1)++f;
    printf("%d\n",f);
}

Nema komentara:

Objavi komentar