#include<stdio.h>
#include<conio.h>
int max(int a, int b) { return (a > b)? a : b; }
int knapSack(int W, int wt[], int pt[], int n){
	if (n == 0 || W == 0)
		 return 0;
	if (wt[n-1] > W)
		 return knapSack(W, wt, pt, n-1);
	else return max( pt[n-1] + knapSack(W-wt[n-1], wt, pt, n-1),
							  knapSack(W, wt, pt, n-1) );
}
/*
//WRITE THIS COMMENTED FUNCTION ONLY IF NEEDED TO UNDERSTAND THE PROCESS OF PICKING
int knapSack(int W, int wt[], int pt[], int n){
	int i, w;
	int K[MAX_SIZE][MAX_SIZE];
	for (i = 0; i <= n; i++){
		 for (w = 0; w <= W; w++){
			  if (i==0 || w==0)
					K[i][w] = 0;
			  else if (wt[i-1] <= w)
					  K[i][w] = max(pt[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]);
			  else
					  K[i][w] = K[i-1][w];
		 }
	}
	return K[n][W];
}
*/
void main(){
	int pt[20],wt[20];
	int W;
	int n,i,j;
	int max_profit;
	int knapSacktems[20];
	int v[20][20];
	clrscr();
	printf("\nENTER THE TOTAL NUMBER OF ITEMS TO INCLUDE\n");
	scanf("%d",&n);

	printf("\nENTER ALL ITEMS WITH ITS WEIGHT AND PROFIT\n");
	for(i=0;i<n;i++){
		scanf("%d%d",&wt[i],&pt[i]);
		knapSacktems[i]=0;
	}
	printf("\nENTER THE MAXIMUM WEIGHT OF THE BAG\n");
	scanf("%d",&W);
	printf("Knapsack Tabulation\n\n");
	printf("p|w\t");
	for(j=0;j<=W;j++){
		printf("%d\t",j);
	}
	printf("\n=====================================================\n");

	for(i=0;i<n;i++){
		printf("%d|%d\t",pt[i],wt[i]);
		for(j=0;j<=W;j++){
			v[i][j]=knapSack(j, wt, pt, i+1);
			printf("%d\t",v[i][j]);
		}
		printf("\n");
	}
	printf("Max profit = %d\n\n",knapSack(W, wt, pt, n));
	printf("Items are selected as shown below\n");
	max_profit=v[n-1][W];
	for(;max_profit>0;){
		for(i=0;i<n;i++){
			for(j=0;j<=W;j++){
				if(v[i][j]==max_profit && max_profit>0){
					knapSacktems[i]=1;
					max_profit=max_profit-pt[i];
					i=-1;
					break;
				}
			}
		}
	}
	for(i=0;i<n;i++){
		printf("K %d = %d\n",i+1,knapSacktems[i]);
	}
	getch();
}