knapsack /unbounded knapsack

http://www.spoj.com/problems/KNAPSACK/    (simple knapsack)

http://www.spoj.com/problems/LKS/         (large knapsack)

Knapsack table filling

#include<stdio.h>

int maxi(int a,int b)
{
    if(a>b)
        return a;
    else
        return b;
}



int main()
{
    int i,h,j,p,mm,summ=0,g,mw;
    scanf("%d",&mw);
    scanf("%d",&h);
int w[h+1],v[h+1];


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



v[0]=0;w[0]=0;


int n[h+1][mw+1];
v[0]=0;w[0]=0;


for(i=0;i<mw+1;i++)
    n[0][i]=0;
for(i=0;i<h+1;i++)
    n[i][0]=0;

for(i=1;i<h+1;i++)
{
    for(j=1;j<mw+1;j++)
    {
        p=j-w[i];
        if(p<0)                                      ///if small just copy the above row element
        {
        n[i][j]=n[i-1][j];
          continue;
        }
     n[i][j]=maxi((v[i]+n[i-1][p]),n[i-1][j]);
    }
}
summ=summ+n[h][mw];

printf("%d\n",summ);



return 0;
}




unbounded knapsack


#include<bits/stdc++.h>

using namespace std;

int findMaxValue(int weight[],int values[],int n,int capacity) {
   // temporary array where index 'j' denotes max value that can be fitted
   // in a knapsack of weight 'j'
   int knapsack[capacity+1];
   knapsack[0] = 0;
   //items[0] = -1;
   int i,j;
   for(j=1;j<=capacity;j++) {
      //items[j] = items[j-1];
      // as per our recursive formula,
      // iterate over all weights w(0)...w(n-1)
      // and find max value that can be fitted in knapsack of weight 'j'
      int max = knapsack[j-1];
      for(i=0;i<n;i++)
        {
         int x = j-weight[i];
         if(x >= 0 && (knapsack[x] + values[i]) > max)
          {
            max = knapsack[x] + values[i];
          }
         knapsack[j] = max;
        }
   }
   return knapsack[capacity];
}


int main()
{
        //freopen("txt.in","r",stdin);
    //freopen("atul.out","w",stdout);

int t;
cin>>t;
while(t--)
{
 long long int n,k,i,m=0,p,pp;
 cin>>n>>k;
int a[n];
 for(i=0;i<n;i++)
  {
   cin>>a[i];
  }

 cout<<findMaxValue(a,a,n,k)<<endl;
}
return 0;
}