Untitled

#include <stdio.h>

void robbery_dp(int num_items, int profit[], int weight[], int capacity, char items[][20]);
int dp_profit(int num_items, int profit[], int weight[], int capacity);
void robbery_greedy(int num_items, int profit[], int weight[], int capacity, char items[][20]);
int greedy_profit(int num_items, int profit[], int weight[], int capacity);
int max(int a, int b);
void display_selected_items(int num_items, int selected[], int profit[], char items[][20]);
void main() {
int i, num_items;
int weight[20], profit[20];
char items[20][20];
int capacity;
printf("A robber wants to rob a house.\n");
printf("We want to find how much profit he can make using two algorithms.\n");
printf("One is the Greedy algorithm and the other is Dynamic Programming.\n");
printf("He cannot take all the items from the house.\n");
printf("Enter the number of items: ");
scanf("%d", &num_items);
printf("Enter the total weight capacity: ");
scanf("%d", &capacity);
printf("Enter the names, weights, and profits of items:\n");
for (i = 1; i <= num_items; i++) {
printf("Name of item %d: ", i);
scanf("%s", items[i]);
printf("Weight of item %d: ", i);
scanf("%d", &weight[i]);
printf("Profit of item %d: ", i);
scanf("%d", &profit[i]);
}
printf("\nUsing Dynamic Programming:\n");
robbery_dp(num_items, profit, weight, capacity, items);

printf("\nUsing Greedy Approach:\n");
robbery_greedy(num_items, profit, weight, capacity, items);

int dp_total_profit = dp_profit(num_items, profit, weight, capacity);
int greedy_total_profit = greedy_profit(num_items, profit, weight, capacity);
printf("\nSummary of results:\n");
printf("Total profit using Dynamic Programming: %d\n", dp_total_profit);
printf("Total profit using Greedy Approach: %d\n", greedy_total_profit);
if (dp_total_profit > greedy_total_profit) {
printf("Dynamic Programming gives a better profit.\n");
} else if (dp_total_profit < greedy_total_profit) {
printf("Greedy Approach gives a better profit.\n");
} else {
printf("Both approaches give the same profit.\n");
}
}

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

void robbery_dp(int num_items, int profit[], int weight[], int capacity, char items[][20]) {
int x[20], v[20][20], i, j;
for (i = 1; i <= num_items; i++) {
x[i] = 0;
}
for (i = 0; i <= num_items; i++) {
v[i][0] = 0;
}
for (i = 0; i <= capacity; i++) {
v[0][i] = 0;
}
for (i = 1; i <= num_items; i++) {
for (j = 1; j <= capacity; j++) {
if (weight[i] > j) {
v[i][j] = v[i - 1][j];
} else {
v[i][j] = max(v[i - 1][j], profit[i] + v[i - 1][j - weight[i]]);
}
}
}
printf("Output using Dynamic Programming:\n");
printf("Profit Table:\n");
for (i = 0; i <= num_items; i++) {

for (j = 0; j <= capacity; j++) {
printf("%d ", v[i][j]);
}
printf("\n");
}
printf("Maximum profit: %d\n", v[num_items][capacity]);
i = num_items;
j = capacity;
while (i != 0) {
if (v[i][j] != v[i - 1][j]) {
x[i] = 1;
j = j - weight[i];
}
i = i - 1;
}
printf("Selected items using Dynamic Programming: ");
display_selected_items(num_items, x, profit, items);
}

int dp_profit(int num_items, int profit[], int weight[], int capacity) {
int v[20][20], i, j;
for (i = 0; i <= num_items; i++) {
for (j = 0; j <= capacity; j++) {
if (i == 0 || j == 0) {
v[i][j] = 0;
} else if (weight[i] > j) {
v[i][j] = v[i - 1][j];
} else {
v[i][j] = max(v[i - 1][j], profit[i] + v[i - 1][j - weight[i]]);
}
}
}
return v[num_items][capacity];
}

void robbery_greedy(int num_items, int profit[], int weight[], int capacity, char items[][20]) {
int i, j, max_index, remaining_capacity = capacity;
int selected[20] = {0};
float ratio[20], max_ratio;
for (i = 1; i <= num_items; i++) {

ratio[i] = (float)profit[i] / weight[i];
}
while (remaining_capacity > 0) {
max_ratio = -1;
max_index = -1;
for (i = 1; i <= num_items; i++) {
if (selected[i] == 0 && ratio[i] > max_ratio) {
max_ratio = ratio[i];
max_index = i;
}
}
if (max_index == -1 || weight[max_index] > remaining_capacity) {
break;
}
selected[max_index] = 1;
remaining_capacity -= weight[max_index];
}
int total_profit = 0;
printf("Selected items using Greedy Approach: ");
for (i = 1; i <= num_items; i++) {
if (selected[i] == 1) {
printf("%s ", items[i]);
total_profit += profit[i];
}
}
printf("\nTotal profit: %d\n", total_profit);
}
int greedy_profit(int num_items, int profit[], int weight[], int capacity) {
int i, j, max_index, remaining_capacity = capacity;
int selected[20] = {0};
float ratio[20], max_ratio;
for (i = 1; i <= num_items; i++) {
ratio[i] = (float)profit[i] / weight[i];
}
while (remaining_capacity > 0) {
max_ratio = -1;
max_index = -1;

for (i = 1; i <= num_items; i++) {
if (selected[i] == 0 && ratio[i] > max_ratio) {
max_ratio = ratio[i];
max_index = i;
}
}
if (max_index == -1 || weight[max_index] > remaining_capacity) {
break;
}
selected[max_index] = 1;
remaining_capacity -= weight[max_index];
}
int total_profit = 0;
for (i = 1; i <= num_items; i++) {
if (selected[i] == 1) {
total_profit += profit[i];
}
}
return total_profit;
}

void display_selected_items(int num_items, int selected[], int profit[], char items[][20]) {
int i;
for (i = 1; i <= num_items; i++) {
if (selected[i]) {
printf("%s (Profit: %d) ", items[i], profit[i]);
}
}
printf("\n");
}