Question$1$

You are given a set of $n$ items, where each item i has

$1)$ A weight wi

A value vi

The total capacity of your knapsack is w$.$

Determine the optimal way to fill the knapsack with a subset of these items to maximize the total value. This means you can take

any portion $01$ of item $i,$ where xi is the fraction of item i taken. The total weight of the selected items $($including

fractions$)$ must not exceed the knapsack's capacity $W.$

Hint: Use merge sort algorithm.

You have been provided with the driver code, with appropriate TODO comments to guide you through the implementation. You have to

only edit merge$(),$ merge$\_$sort$(),$ and knapsack$()$ subroutines in the file student$\_$file.c$.$ You have been provided with the driver

code in the main$()$ function in the same file. DO NOT MODIFY ANY LINES OF THE FILE APART FROM WITHIN THE FUNCTION merge$(),$

merge$\_$sort$(),$ and knapsack$(),$ else your assignment will not be evaluated. You are free to add other functions if you wish to$.$

Note: The example input given here differs from the test cases checked when the code is submitted.

code

#include

#include

$//$ Define a structure for items

typedef struct

$\{$

int weight;

int value;

double ratio;

$\}$ Item;

$//$ Function prototypes

void merge$\_$sort$($Item items$[],$ int left, int right$)$;

void merge$($Item items$[],$ int left, int mid, int right$)$;

double knapsack$($Item items$[],$ int n$,$ int capacity$)$;

$//$ Main function

int main$()$

$\{$

int n$,$ capacity;

$//$ User inputs

scanf$("\%$d$",$ &n$)$;

Item items$[$n$]$;

for $($int i $=0$; i $$ n; i$++)$

$\{$

scanf$("\%$d $\%$d$",$ &items$[$i$].$value, &items$[$i$].$weight$)$;

items$[$i$].$ratio $=($double$)$items$[$i$].$value $/$ items$[$i$].$weight;

$\}$

scanf$("\%$d$",$ &capacity$)$;

$//$ Calculate the maximum value

double max$\_$value $=$ knapsack$($items$,$ n$,$ capacity$)$;

printf$("\%\mathrm{.}2$f

$",$ max$\_$value$)$;