knapsack
#include <stdio.h>
float Knapsack(int size, int p[], int w[], float ratio[], int m) {
float b = 0;
int i = 0;
for (i = 0; i < size; i++) {
if (m > 0 && w[i] <= m) {
m = m - w[i];
b = b + p[i];
} else {
break;
}
}
if (m > 0) {
b = b + ((float)p[i] * m / w[i]);
}
return b;
}
void sort(int size, int p[], int w[], float ratio[]) {
for (int i = 0; i < size; i++) {
for (int j = i; j < size; j++) {
if (ratio[i] < ratio[j]) {
float temp1 = ratio[i];
ratio[i] = ratio[j];
ratio[j] = temp1;
int temp2 = p[i];
p[i] = p[j];
p[j] = temp2;
int temp = w[i];
w[i] = w[j];
w[j] = temp;
}
}
}
}
int main() {
int size;
printf("Enter The size of array: ");
scanf("%d", &size);
int p[size];
int w[size];
float ratio[size];
printf("Enter the profit object: ");
for (int i = 0; i < size; i++) {
scanf("%d", &p[i]);
}
printf("\nEnter the weight object: ");
for (int i = 0; i < size; i++) {
scanf("%d", &w[i]);
}
printf("\nratio:\n");
for (int i = 0; i < size; i++) {
ratio[i] = (float)p[i] / (float)w[i];
printf("%f ", ratio[i]);
}
int Km;
printf("\n\nKnapsack Size: ");
scanf("%d", &Km);
sort(size, p, w, ratio);
printf("\n\ncheck\n");
printf("profit: ");
for (int i = 0; i < size; i++) {
printf("%d ", p[i]);
}
printf("\nweight: ");
for (int i = 0; i < size; i++) {
printf("%d ", w[i]);
}
printf("\nratio: ");
for (int i = 0; i < size; i++) {
printf("%f ", ratio[i]);
}
float a = Knapsack(size, p, w, ratio, Km);
printf("\nmax profit: %f\n", a);
return 0;
}
Comments
Post a Comment