ADA Greedy

#include <stdio.h>

#include <stdlib.h>

// Function to find the maximum of two integers
int max(int a, int b) {
return (a > b) ? a : b;
}
// Function to solve the knapsack problem using dynamic programming
void knapsack(int n, int c, int p[], int w[]) {
int v[n+1][c+1];
// Build the DP table in bottom-up manner
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= c; j++) {
if (i == 0 || j == 0) {
v[i][j] = 0;
} else if (w[i-1] <= j) {
v[i][j] = max(v[i-1][j], p[i-1] + v[i-1][j-w[i-1]]);
} else {
v[i][j] = v[i-1][j];
}
}
}
// Print the optimal solution
printf("Optimal Solution: %d\n", v[n][c]);
// Print the items included in the knapsack
printf("The objects picked up into the knapsack are: ");
int i = n, j = c;
while (i > 0) {
if (v[i][j] != v[i-1][j]) {
printf("%d ", i);
j -= w[i-1];
}
i--;
}
printf("\n");
}
int main() {
int n, c;
// Input for number of objects
printf("Enter the number of objects: ");
scanf("%d", &n);

if (n <= 0) {

printf("The number of objects must be a positive integer.\n");
return 1;
}
// Input for knapsack capacity
printf("Enter the capacity of the knapsack: ");
scanf("%d", &c);
if (c <= 0) {
printf("The capacity of the knapsack must be a positive integer.\n");
return 1;
}
int p[n], w[n];
// Input for profits
printf("Enter the profit for each of the %d objects: \n", n);
for (int i = 0; i < n; i++) {
scanf("%d", &p[i]);
if (p[i] < 0) {
printf("Profit must be a non-negative integer.\n");
return 1;
}
}
// Input for weights
printf("Enter the weight for each of the %d objects: \n", n);
for (int i = 0; i < n; i++) {
scanf("%d", &w[i]);
if (w[i] < 0) {
printf("Weight must be a non-negative integer.\n");
return 1;
}
}
// Solve the knapsack problem
knapsack(n, c, p, w);
return 0;
}