Write a program to solve 0/1 Knapsack problem Using Dynamic Programming.

 #include <stdio.h>

// Function to return max of two numbers

int max(int a, int b) {

    return (a > b) ? a : b;

}

// Function to solve 0/1 Knapsack problem using DP

int knapsack(int W, int wt[], int val[], int n) {

    int i, w;

    int dp[n + 1][W + 1];

    // Build dp table

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

        for (w = 0; w <= W; w++) {

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

                dp[i][w] = 0;

            else if (wt[i - 1] <= w)

                dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]],

                               dp[i - 1][w]);

            else

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

        }

    }

    return dp[n][W];

}

// Main function

int main() {

    int val[] = {60, 100, 120};      // values of items

    int wt[] = {10, 20, 30};         // weights of items

    int W = 50;                      // Capacity of knapsack

    int n = sizeof(val) / sizeof(val[0]);

    int maxProfit = knapsack(W, wt, val, n);

    printf("Maximum value that can be taken = %d\n", maxProfit);

    return 0;

}

Output: