Design and implement C/C++ Program to solve 0/1 Knapsack problem using Dynamic Programming method.
#include <stdio.h>
// Function to find the maximum of two integers
int max(int a, int b) {
return (a > b)? a : b;
}
// Function to solve 0/1 Knapsack problem using Dynamic Programming
int knapsack(int W, int weight[], int value[], int n) {
int i, w;
// Create a 2D array (table) to store maximum value at each n and W
int V[n + 1][W + 1];
// Build table V[][] in bottom-up manner
for (i = 0; i <= n; i++) {
for (w = 0; w <= W; w++) {
// Base case: if no item or capacity is 0, value is 0
if (i == 0 || w == 0) {
V[i][w] = 0;
}
// If weight of the current item is more than the current capacity
else if (weight[i - 1] > w) {
V[i][w] = V[i - 1][w]; // Can't include the item
}
// Else, take the maximum of including or not including the item
else {
V[i][w] = max(V[i - 1][w], value[i - 1] + V[i - 1][w - weight[i - 1]]);
}
}
}
// V[n][W] contains the maximum value that can be put in the knapsack
return V[n][W];
}
int main() {
int n, W, i;
// Input: number of items
printf("Enter number of items: ");
scanf("%d", &n);
int value[n], weight[n];
// Input: values and weights of each item
printf("Enter value and weight of each item:\n");
for (i = 0; i < n; i++) {
printf("Item %d:\n", i + 1);
printf("Value: ");
scanf("%d", &value[i]);
printf("Weight: ");
scanf("%d", &weight[i]);
}
// Input: maximum capacity of knapsack
printf("Enter capacity of knapsack: ");
scanf("%d", &W);
// Call the knapsack function and print the result
int max_value = knapsack(W, weight, value, n);
printf("Maximum value that can be put in the knapsack = %d\n", max_value);
return 0;
}
OUTPUT
Enter number of items: 4
Enter value and weight of each item:
Item 1:
Value: 12
Weight: 2
Item 2:
Value: 10
Weight: 1
Item 3:
Value: 20
Weight: 3
Item 4:
Value: 15
Weight: 2
Enter capacity of knapsack: 5
Maximum value that can be put in the knapsack = 37