def knapsack_tabulation():

    n = len(values)

    tab = [[0] * (capacity + 1) for _ in range(n + 1)]

​

    for i in range(1, n + 1):

        for w in range(1, capacity + 1):

            if weights[i-1] <= w:

                include_item = values[i-1] + tab[i-1][w - weights[i-1]]

                exclude_item = tab[i-1][w]

                tab[i][w] = max(include_item, exclude_item)

            else:

                tab[i][w] = tab[i-1][w]

​

    for row in tab:

        print(row)

​

    items_included = []

    w = capacity

    for i in range(n, 0, -1):

        if tab[i][w] != tab[i-1][w]:

            items_included.append(i-1)

            w -= weights[i-1]

​

    print("\nItems included:", items_included)

​

    return tab[n][capacity]

​

values = [300, 200, 400, 500]

weights = [2, 1, 5, 3]

capacity = 10

print("\nMaximum value in Knapsack =", knapsack_tabulation())

​

#Python

#include <stdio.h>

​

int values[] = {300, 200, 400, 500};

int weights[] = {2, 1, 5, 3};

int capacity = 10;

int n = 4;

​

int knapsackTabulation() {

    int tab[n + 1][capacity + 1];

    for (int i = 0; i <= n; i++) {

        for (int w = 0; w <= capacity; w++) {

            if (i == 0 || w == 0) {

                tab[i][w] = 0;

            } else if (weights[i - 1] <= w) {

                int includeItem = values[i - 1] + tab[i - 1][w - weights[i - 1]];

                int excludeItem = tab[i - 1][w];

                tab[i][w] = (includeItem > excludeItem) ? includeItem : excludeItem;

            } else {

                tab[i][w] = tab[i - 1][w];

            }

        }

    }

​

    // Print the DP table

    for (int i = 0; i <= n; i++) {

        for (int w = 0; w <= capacity; w++) {

            printf("%d ", tab[i][w]);

        }

        printf("\n");

    }

​

    // Backtrack to find the items included

    int w = capacity;

    printf("\nItems included:");

    for (int i = n; i > 0; i--) {

        if (tab[i][w] != tab[i - 1][w]) {

            printf(" %d", i - 1);

            w -= weights[i - 1];

        }

    }

    printf("\n");

​

    return tab[n][capacity];

import java.util.ArrayList;

import java.util.List;

​

public class Main {

    private static int[] values = {300, 200, 400, 500};

    private static int[] weights = {2, 1, 5, 3};

    private static int capacity = 10;

​

    private static int knapsackTabulation() {

        int n = values.length;

        int[][] tab = new int[n + 1][capacity + 1];

​

        // Populate the DP table

        for (int i = 1; i <= n; i++) {

            for (int w = 1; w <= capacity; w++) {

                if (weights[i - 1] <= w) {

                    int includeItem = values[i - 1] + tab[i - 1][w - weights[i - 1]];

                    int excludeItem = tab[i - 1][w];

                    tab[i][w] = Math.max(includeItem, excludeItem);

                } else {

                    tab[i][w] = tab[i - 1][w];

                }

            }

        }

​

        // Print the DP table

        for (int[] row : tab) {

            for (int num : row) {

                System.out.print(num + " ");

            }

            System.out.println();

        }

​

        // Backtrack to find the items included

        List<Integer> itemsIncluded = new ArrayList<>();

        int w = capacity;

        for (int i = n; i > 0; i--) {

            if (tab[i][w] != tab[i - 1][w]) {

                itemsIncluded.add(i - 1);

                w -= weights[i - 1];

            }

        }

​

        System.out.println("\nItems included: " + itemsIncluded);