#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) );
}

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();
}