UVA 10130 - SuperSale(cpp file)

Problem Type : DP(0-1 KNEPSECK)



#include<stdio.h>
#include<string.h>
#define MAX 1000
int V[MAX][MAX];
int  knepseck(int v[],int w[],int n,int W)
{
    int i,j;
    for(i=0; i<=W; i++)
    {
        V[0][i]=0;
    }
    for(i=1; i<=n; i++)
    {
        for(j=0; j<=W; j++)
        {
            if(w[i]<=j)
            {
                int p= V[i-1][j];
                int q=v[i]+V[i-1][j-w[i]];
                if(p>q)
                {
                    V[i][j]=p;
                }
                else
                {
                    V[i][j]=q;
                }
            }
            else
            {
                V[i][j]=V[i-1][j];
            }
        }
    }

    return V[n][W] ;
}
int main()
{
    int n,v[MAX],w[MAX],W,solution,i,test,people,m;
    scanf("%d",&test);
    while(test--)
    {

        scanf("%d",&n);

        for(i=1; i<=n; i++)
        {
            scanf("%d %d",&v[i],&w[i]);
        }
        W=0;

        scanf("%d",&people);
        for(i=1;i<=people;i++)
        {
            scanf("%d",&m);
            W+=knepseck(v,w,n,m);
        }
        printf("%d\n",W);;
    }

}