Untitled
#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