A Dynamic Programming based solution to the 0-1 Knapsack problem.

0-1knapsack.c

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

//Returns the maximum of two integers
int max(int a,int b){

	if(a > b)
		return a;
	else 
		return b;
}

int knapsack(int n,int wmax,int val[],int wt[]){
	int i,w;
	int T[n+1][wmax+1];
	//Building table T[][] with (row = total items +1) & (column = total weight + 1)
	for(i=0;i<=n;i++){
		for(w=0;w<=wmax;w++){
			if(i == 0 || w == 0)
				T[i][w] = 0;

			else if(wt[i-1] <= w){
			
				T[i][w] = max((val[i-1] + T[i-1][w - wt[i-1]]),(T[i-1][w]));
			}

			else{

				T[i][w] = T[i-1][w];
			}

		}
		
	}
	return T[n][wmax];
}
	
		
int main(){

	int num,i,wmax;
	printf("\nEnter the number of items: ");
	scanf("%d",&num);
	int val[num], wt[num];
	printf("\nEnter the maximum weight of the knapsack: ");
	scanf("%d",&wmax);
	printf("\nEnter the value and the weight of the items  - ");
	for(i = 0;i < num;i++){
		printf("\nValue: ");
		scanf("%d",&val[i]);
		printf("\nWeight: ");
		scanf("%d",&wt[i]);
	}

	printf("\nThe items are: ");
	printf("\nValue:   ");
	for(i=0;i<num;i++){
		printf("%d     ",val[i]);
	}
	printf("\nWeight:  ");
	for(i=0;i<num;i++)
		printf("%d     ",wt[i]);
	printf("\n");
	int result = knapsack(num,wmax,val,wt);
	printf("\nThe maximum value that can be knapsacked:  %d\n",result);
	return 0;
}