/* 5(a). Given a knapsack of capacity M, and n objects of weights (w1,w2,....,wn) with profits (p1,p2,.....,pn). W.A.P. to implement greedy knapsack that provides maximum profit. */

#include<stdio.h>
#include<conio.h>
int n,p[30],w[30],t[30]; /* No. of objects,profit & weight of n object(s) */
void Sort(void)
{
    int pass,i,j;
    for (i = 1; i <= n; i++)
        t[i] = i; /* Points to respective objects */
    for (pass = 1; pass < n; pass++)
        for (j = 1; j < n; j++)
            if ((float)p[t[j]] / w[t[j]] < (float)p[t[j+1]] / w[t[j+1]])
            {
                int temp = t[j];
                t[j] = t[j+1];
                t[j+1] = temp;
            }
}
float Knapsack(int m, float x[])
{
    int i,cu = m;
    float maxprofit = 0;
    Sort();
    for (i = 1; i <= n; i++)
    {
        if (w[t[i]] > cu) break;
            x[t[i]] = 1.0;
            cu -= w[t[i]];
            maxprofit += p[t[i]];
    }
    if (i <= n)
    {
        x[t[i]] = (float) cu / w[t[i]];
        maxprofit += x[t[i]] * p[t[i]];
        return maxprofit;
    }
    return;
}
void main()
{
    float svector[30],optsoln; /* Solution vector, Optimal solution */
    int m,cu,i; /* No. of objects, Knapsack size */
    clrscr();    
    printf("Enter no. of objects : ");
    scanf("%d",&n);
    printf("\nEnter the weights :\n");
        for (i = 1; i <= n; i++)
            scanf("%d",&w[i]);
            printf("\nEnter the profits :\n");
        for (i = 1; i <= n; i++)
        {
            scanf("%d",&p[i]);
            svector[i] = 0.0;
        }
    printf("\nEnter the knapscak capacity : ");
    scanf("%d",&m);
    optsoln=Knapsack(m,svector);
    printf("\nOptimal solution is %4.2f",optsoln);
    printf("\nSolution vector is as follows :\n");
        for (i = 1; i <= n; i++)
            printf("%4.2f ",svector[i]);
            getch();
}
/* OUTPUT
Enter no. of objects : 3

Enter the weights :
18 15 10

Enter the profits :
25 24 15

Enter the knapsack capacity : 20

Optimal solution is 31.50
The solution vector is as follows :
0.00 1.00 0.50
*/