ADA Program 6

 

 6. 0/1 Knapsack (Dynamic Programming)

/* Program to solve 0/1 Knapsak problem using Dynamic Programming method.*/

#include<stdio.h>

int knapSack(int capacity, int weight[], int value[], int n) {
    int dp[n + 1][capacity + 1];
    
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 0;
    }
    for (int w = 0; w <= capacity; w++) {
        dp[0][w] = 0;
    }
    
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= capacity; w++) {
            if (weight[i-1] <= w) {
                dp[i][w] = (value[i-1] + dp[i-1][w - weight[i-1]]) > dp[i-1][w]
                    ? (value[i-1] + dp[i-1][w - weight[i-1]]) : dp[i-1][w];
            } else {
                dp[i][w] = dp[i-1][w];
            }
        }
    }
    return dp[n][capacity];
}

int main() {
    int n, capacity;
    printf("Enter number of items: ");
    scanf("%d", &n);
    int weight[n], value[n];
    printf("Enter %d weights: ", n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &weight[i]);
    }
    printf("Enter %d values/profits: ", n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &value[i]);
    }
    printf("Enter knapsack capacity: ");
    scanf("%d", &capacity);
    printf("Maximum value: %d\n", knapSack(capacity, weight, value, n));
    return 0;
}