Untitled

 avatar
unknown
plain_text
a month ago
1.2 kB
2
Indexable
#include <stdio.h>

int max(int a, int b) {
    return (a > b) ? a : b;
}

int main() {
    int N = 4; // Number of items
    int W = 5; // Capacity of the bag
    int p = 2; // Penalty for not picking an item
    int val[] = {5, 6, 3, 7}; // Values of items
    int wt[] = {1, 2, 3, 4};  // Weights of items

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

    // Initialize DP table
    for (int i = 0; i <= N; i++) {
        for (int w = 0; w <= W; w++) {
            if (i == 0 || w == 0) {
                dp[i][w] = 0;
            } else if (wt[i - 1] <= w) {
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - wt[i - 1]] + val[i - 1]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    // Calculate penalty
    int totalPenalty = 0;
    for (int i = 0; i < N; i++) {
        int itemIncluded = 0;
        for (int w = 0; w <= W; w++) {
            if (dp[i + 1][w] != dp[i][w]) {
                itemIncluded = 1;
                break;
            }
        }
        if (!itemIncluded) {
            totalPenalty += p;
        }
    }

    int maxNetValue = dp[N][W] - totalPenalty;

    printf("Net Value: %d\n", maxNetValue);
    return 0;
}
Leave a Comment