{"id":828,"date":"2024-10-14T14:25:03","date_gmt":"2024-10-14T08:55:03","guid":{"rendered":"https:\/\/codexplained.in\/?p=828"},"modified":"2025-11-24T15:42:58","modified_gmt":"2025-11-24T10:12:58","slug":"0-1-knapsack-problem-using-dynamic-programming","status":"publish","type":"post","link":"https:\/\/codexplained.in\/?p=828","title":{"rendered":"0\/1 Knapsack Problem using Dynamic Programming"},"content":{"rendered":"\n

Problem Statement<\/h3>\n\n\n\n

Given a set of items, each with a weight and a value, you need to find the maximum value you can carry in a knapsack of a fixed capacity.<\/p>\n\n\n\n

Key Concepts<\/h3>\n\n\n\n
    \n
  1. Dynamic Programming<\/strong>: This method breaks down the problem into simpler subproblems and builds up solutions to larger problems based on the solutions to smaller ones.<\/li>\n\n\n\n
  2. State Representation<\/strong>: We use a 2D array dp<\/code> where dp[i][w]<\/code> represents the maximum value that can be attained with a maximum weight w<\/code> using the first i<\/code> items.<\/li>\n<\/ol>\n\n\n\n

    Dynamic Programming Approach<\/h3>\n\n\n\n
      \n
    • Step 1<\/strong>: Initialize a 2D array dp<\/code> where the rows represent items and the columns represent weights from 0<\/code> to the maximum capacity.<\/li>\n\n\n\n
    • Step 2<\/strong>: Iterate over each item and each weight to fill the dp<\/code> table based on whether to include or exclude the item.<\/li>\n\n\n\n
    • Step 3<\/strong>: The maximum value will be found in dp[n][W]<\/code>, where n<\/code> is the number of items and W<\/code> is the maximum capacity.<\/li>\n<\/ul>\n\n\n\n

      C Program for 0\/1 Knapsack Problem<\/h3>\n\n\n
      \n#include <stdio.h>\n#include <stdlib.h>\n\n\/\/ Function to solve the 0\/1 Knapsack Problem\nint knapsack(int W, int weights[], int values[], int n) {\n    int** dp = (int**)malloc((n + 1) * sizeof(int*));\n    for (int i = 0; i <= n; i++) {\n        dp[i] = (int*)malloc((W + 1) * sizeof(int));\n    }\n\n    \/\/ Build the dp table\n    for (int i = 0; i <= n; i++) {\n        for (int w = 0; w <= W; w++) {\n            if (i == 0 || w == 0) {\n                dp[i][w] = 0; \/\/ Base case\n            } else if (weights[i - 1] <= w) {\n                \/\/ Max of including the item or not\n                dp[i][w] = (values[i - 1] + dp[i - 1][w - weights[i - 1]] > dp[i - 1][w]) ?\n                            values[i - 1] + dp[i - 1][w - weights[i - 1]] : dp[i - 1][w];\n            } else {\n                dp[i][w] = dp[i - 1][w]; \/\/ Cannot include the item\n            }\n        }\n    }\n\n    \/\/ Get the maximum value from the last cell\n    int maxValue = dp[n][W];\n\n    \/\/ Free the allocated memory\n    for (int i = 0; i <= n; i++) {\n        free(dp[i]);\n    }\n    free(dp);\n\n    return maxValue;\n}\n\n\/\/ Main function\nint main() {\n    int n, W;\n\n    \/\/ Input the number of items\n    printf("Enter the number of items: ");\n    scanf("%d", &n);\n\n    int* weights = (int*)malloc(n * sizeof(int));\n    int* values = (int*)malloc(n * sizeof(int));\n\n    \/\/ Input the weights and values\n    printf("Enter the weights of the items: ");\n    for (int i = 0; i < n; i++) {\n        scanf("%d", &weights[i]);\n    }\n\n    printf("Enter the values of the items: ");\n    for (int i = 0; i < n; i++) {\n        scanf("%d", &values[i]);\n    }\n\n    \/\/ Input the maximum capacity of the knapsack\n    printf("Enter the maximum capacity of the knapsack: ");\n    scanf("%d", &W);\n\n    \/\/ Calculate the maximum value that can be carried\n    int maxValue = knapsack(W, weights, values, n);\n    printf("Maximum value in the knapsack: %d\\n", maxValue);\n\n    \/\/ Free the allocated memory\n    free(weights);\n    free(values);\n\n    return 0;\n}\n\n<\/pre><\/div>\n\n\n
      Explanation of the Code<\/h3>\n\n\n\n
        \n
      1. Dynamic Programming Table<\/strong>:\n
          \n
        • We create a 2D array dp<\/code> where dp[i][w]<\/code> stores the maximum value for the first i<\/code> items and a maximum weight of w<\/code>.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
        • Filling the DP Table<\/strong>:\n
            \n
          • We iterate through the items and weights. For each item, we check if we can include it in the knapsack. If the current item’s weight is less than or equal to the current weight w<\/code>, we have the option to include it or not. If we exclude it, we take the value from the previous item.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
          • Maximum Value Extraction<\/strong>:\n
              \n
            • After populating the dp<\/code> array, the maximum value that can be carried is found at dp[n][W]<\/code>.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
            • Memory Management<\/strong>:\n
                \n
              • The program dynamically allocates memory for the weights, values, and dp<\/code> table, and frees that memory at the end to prevent memory leaks.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n
                Input and Output Example<\/h3>\n\n\n\n
                Input<\/h4>\n\n\n\n
                mathematicaCopy codeEnter the number of items: 4\nEnter the weights of the items: 1 2 3 2\nEnter the values of the items: 20 5 10 40\nEnter the maximum capacity of the knapsack: 5\n<\/code><\/pre>\n\n\n\n
                Output<\/h4>\n\n\n\n
                yamlCopy codeMaximum value in the knapsack: 60\n<\/code><\/pre>\n\n\n\n
                Explanation of the Output<\/h3>\n\n\n\n
                In this example, the maximum value of 60<\/code> can be achieved by including items with weights 2<\/code> and 3<\/code>, which have values 40<\/code> and 20<\/code> respectively.<\/p>\n\n\n\n
                Conclusion<\/h3>\n\n\n\n
                This C program effectively solves the 0\/1 Knapsack Problem using dynamic programming. It allows for user input for flexibility and computes the maximum value that can be placed in the knapsack given specific weights and values. You can test different sets of items and capacities to see how the optimal solution changes. This approach is widely applicable in resource allocation problems.<\/p>\n