nedelja 8

#include <stdio.h>
#include <stdlib.h>

int fibRec(int n)
{
    if(n==0 || n==1)
    {
        return 1;
    }
    else
    {
        return fibRec(n-1)+fibRec(n-2);
    }
}


int fd1[1000];
int fibDin1(int n)
{
     if(n==0 || n==1)
    {
        return 1;
    }
    else
    {
        if(fd1[n]==0)
        {
            int temp=fibDin1(n-1)+fibDin1(n-2);
            fd1[n]=temp;
            return temp;
        }
        return fd1[n];
    }
}


int fibDin2(int n)
{
    int* fib=malloc((n+1)*sizeof(int));
    fib[0]=1;
    fib[1]=1;

    int i;
    for(i=2;i<=n;i++)
    {
        fib[i]=fib[i-1]+fib[i-2];
    }
    return fib[n];
}

//naci min cijenu puta od gornjeg lijevog do donjeg desnog
// ako su moguci potezi dolje i desno
int minPut(int** mat, int m, int n)
{

    int matP[m][n];
    matP[0][0]=mat[0][0];

    int i,j;
    for(j=1;j<n;j++)
    {
        matP[0][j]=matP[0][j-1]+mat[0][j];
    }
    for(i=1;i<m;i++)
    {
        matP[i][0]=matP[i-1][0]+mat[i][0];
    }
    for(j=1;j<n;j++)
    {
        for(i=1;i<m;i++)
        {
            if(matP[i-1][j]<matP[i][j-1])
                 matP[i][j]=matP[i-1][j]+mat[i][j];
            else
                 matP[i][j]=matP[i][j-1]+mat[i][j];
        }
    }

    return matP[m-1][n-1];
}

int KnapSackA(int *z, int* v, int n, int q)
{
    if(q==0)
    {
        return 0;
    }
    if(n==1)
    {
        if(z[0]<=q)
            return v[0];
        return 0;
    }
    int temp1=0,temp2=0;
    if(z[n-1]<=q)
    {
        temp1=v[n-1]+KnapSackA(z,v,n-1,q-z[n-1]);
    }
    temp2=KnapSackA(z,v,n-1,q);
    if(temp1>temp2)
        return temp1;
    return temp2;
}

int KnapSackB(int *z, int* v, int n, int q)
{
     if(q==0)
    {
        return 0;
    }
        if(n==0)
    {
        if(z[0]<=q)
            return v[0];
        return 0;
    }
    int temp1=0,temp2=0;
    if(z[n-1]<=q)
    {
        temp1=v[n-1]+KnapSackB(z,v,n,q-z[n-1]);
    }
    temp2=KnapSackB(z,v,n-1,q);
    if(temp1>temp2)
        return temp1;
    return temp2;
}


int main()
{

//int i,n;
/*for(i=0;i<=n;i++)
{
    fd1[i]=0;
}

printf("%d. fibonacci broj je: %d",41,fibDin2(41));
*/

/* FILE* f= fopen("rob.txt","r");

    int m,n;
    fscanf(f,"%d %d",&m,&n);

    int **mat;
    mat=malloc(m*sizeof(int*));
    int i;

    for(i=0;i<m;i++)
        mat[i]=malloc((n*sizeof(int)));

    int j;
    for(i=0;i<m;i++)
    {
        for(j=0;j<n;j++)
            fscanf(f,"%d",&mat[i][j]);

    }

printf("%d\n", minPut(mat,m,n));
*/

int n=4,q=20;
int z[]={1,2,3,4};
int v[]={2,5,8,10};

printf("%d\n",KnapSackB(z,v,n,q));


    return 0;
}