# include
void knapsack(int n, float w[], float p[], float m){
float x[20], tp= 0;
int i, j, u;
for (i=0; i < n; i++ ){
x[i]=0.0;
}
u=m;
for (i=0; i < n; i++ ){
if(w[i]>u)
break;
else{
x[i]=1.0;
tp= tp+p[i];
u=u-w[i];
}
if(i < n){
x[i]=u/w[i];
}
tp= tp + (x[i]*p[i]);
printf("\n The path is: ");
for(i=0; i < n; i++ ){
printf("%f\t",x[i]);
}
printf("\n Maximum profit is: %f", tp);
}
float swap(float *a, float *b){
float temp;
temp= *a;
*a= *b;
*b= temp;
}
}
int main(){
float w[20], p[20], m;
int n, i ,j;
float ratio[20], temp;
printf ("\n Enter the number of objects: ");
scanf ("%d", &n);
printf ("\n Enter the weights and profits of each object: ");
for (i=0; i < n; i++){
scanf("%f %f", &w[i], &p[i]);
}
printf ("\nEnter the size of knapsack: ");
scanf ("%f", &m);
for (i=0; i < n; i++){
ratio[i]=p[i]/w[i];
}
for( i=0; i < n; i++ ){
for(j=i+1; j < n; j++){
if(ratio[i] < ratio[j]){
swap(&ratio[i], &ratio[j]);
swap(&w[i], &w[j]);
swap(&p[i], &p[j]);
}
}
}
knapsack(n, w, p, m);
}
Main Menu
▼
Pages
▼
No comments:
Post a Comment