0-1 Knapsack Code

#define MAX_ITEMS 20
#define CAPACITY  5000

int V[MAX_ITEMS+1][CAPACITY+1], K[MAX_ITEMS+1][CAPACITY+1] ;

/* Find a solution to maximizing VALUE while subjected to a maximum WEIGHT of W */
/* values[n+1] = {0, v1, v2, ...vn} ;
   weights[n+1] = {0, w1, w2, ... wn} ;
   n = total number of items
   W = maximum capacity of the knapsack
*/
int knapsack01(int W, int n, int values[MAX_ITEMS+1], int weights[MAX_ITEMS+1])
{
   int i, j, w, t, sol[MAX_ITEMS+1] ;

   for (w=0; w<=W; w++)
      V[0][w] = 0 ;

   for (i=1; i<=n; i++) {
      for (w=0; w<=W; w++) {
         if (weights[i]<=w) {
            t = values[i] + V[i-1][w-weights[i]] ;
            if (V[i-1][w] > t) {
               V[i][w] = V[i-1][w] ;
               K[i][w] = 0 ;
            }
            else {
               V[i][w] = t ;
               K[i][w] = 1 ;
            }
         }
         else {
            V[i][w] = V[i-1][w] ;
            K[i][w] = 0 ;
         }
      }
   }

   t = W ;
   for (i=n, j=0; i>=1; i--) {
      if (K[i][t]==1) {
         sol[j++] = values[i] ;
         t = t-weights[i] ;
      }
   }

   for (--j; j>=0; j--)
      printf("%d ", sol[j]) ;

   return V[n][W] ;
}

Maximum 1-D Sum

#include <stdio.h>
#define MAX_N     100

int dp_max(int a, int b)
{
     return (a > b) ? a : b ;
}

/*
  * Problem - Maximum Value Contiguous Subsequence / Maximum 1-D sum
  * From a sequence of n integers a(1) ... a(n), determine a 
  * contiguous sub-sequence a(i) ... a(j) having the maximum sum of 
  * its elements.
  *
*/
int dp_max_contiguous_subseq(int *arr, int len)
{
     int i, j, m[MAX_N], max,
          s=0,     /* index of start of the sub-sequence */
          e=0 ;     /* index of end of the sub-sequence */

     if (arr[0]<0) max = 0 ;
     else max = arr[0] ;

     for (m[0]=arr[0], j=1; j<len; j++) {
          m[j] = dp_max(m[j-1]+arr[j], arr[j]) ;
          if (m[j]>=max) {
               max = m[j] ;
               e = j ;
               if (m[j] == arr[j])
                    s = j ;
          }
     }

     printf("\n\nMax Contiguous Sequence starts@ %d and ends@ %d and sums to %d\n", s, e, max) ;

     return max ;
}

int main()
{
     int i, arr[MAX_N] ;

     #ifndef ONLINE_JUDGE
     freopen("dp_max_contiguous_subseq.in", "r", stdin) ;
     #endif

     i = 0 ;
     while (scanf("%d", &arr[i]) != EOF) i++ ;
     dp_max_contiguous_subseq(arr, i) ;

     return 0;
}