#include <stdio.h>
#include <stdlib.h>
#define MAX(a, b) ((a) > (b) ? (a) : (b))
int knapsack(int W, int wt[], int val[], int n) {
int i, w, K[n+1][W+1];
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(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
else
K[i][w] = K[i-1][w];
}}
// Backtrack to find items
int res = K[n][W];
w = W;
for (i = n; i > 0 && res > 0; i--) {
if (res != K[i-1][w]) {
printf("Item %d is included\n", i);
res -= val[i-1];
w -= wt[i-1];
}}
return K[n][W];
}
int main() {
int val[] = {10, 4, 9, 11};
int wt[] = {3, 5, 6, 2};
int W = 7;
int n = sizeof(val) / sizeof(val[0]);
printf("Maximum value: %d\n", knapsack(W, wt, val, n));
return 0;
}