0/1 Knapsack Problem in C
Introduction
The 0/1 knapsack problem is a classic problem in computer science and operations research that involves finding the optimal way to pack a set of items of different weights and values into a knapsack of limited capacity. The problem is called 0/1 because each item can either be included (1) or excluded (0) from the knapsack.
Problem Statement
Given a set of items, each with a weight w_i and a value v_i, and a knapsack with a capacity W, the goal is to select a subset of the items to include in the knapsack such that the total weight of the selected items does not exceed the knapsack capacity and the total value of the selected items is maximized.
Dynamic Programming Solution
The 0/1 knapsack problem can be solved using dynamic programming, which is a method for solving complex problems by breaking them down into smaller subproblems and solving each subproblem only once.
Here is an example of C code that implements a dynamic programming solution to the 0/1 knapsack problem:
#include
#include
int knapsack(int W, int n, int *w, int *v) {
int i, wt;
int K[n + 1][W + 1];
// Build table K[][] in bottom up manner
for (i = 0; i <= n; i++) {
for (wt = 0; wt <= W; wt++) {
if (i == 0 || wt == 0)
K[i][wt] = 0;
else if (w[i - 1] <= wt)
K[i][wt] = fmax(v[i - 1] + K[i - 1][wt - w[i - 1]], K[i - 1][wt]);
else
K[i][wt] = K[i - 1][wt];
}
}
return K[n][W];
}
int main() {
int W = 50;
int n = 3;
int w[] = {10, 20, 30};
int v[] = {60, 100, 120};
printf("Maximum value that can be put in a knapsack of capacity %d is %d\n", W, knapsack(W, n, w, v));
return 0;
}
Explanation
In this code, we define a 2D array K of size (n + 1) x (W + 1), where n is the number of items and W is the knapsack capacity. The array K is used to store the maximum value that can be obtained with a given weight wt and a given number of items i.
The outer loop iterates over each item, and the inner loop iterates over each possible weight from 0 to W. For each item and weight, we calculate the maximum value that can be obtained by either including or excluding the current item.
If the current item's weight is less than or equal to the current weight wt, we consider two options: including the current item and excluding it. We choose the option that gives the maximum value.
Finally, we return the maximum value that can be obtained with the full knapsack capacity W.
Time Complexity
The time complexity of this dynamic programming solution is O(nW), where n is the number of items and W is the knapsack capacity.
Conclusion
In this article, we discussed the 0/1 knapsack problem and implemented a dynamic programming solution in C. The solution has a time complexity of O(nW) and can be used to solve small to medium-sized instances of the problem.
