Now consider the following practical problem Suppose that yo

Now, consider the following practical problem. Suppose that you\'re in charge of picking a set of experiments to be launched into space. Each experiment has an ID number, an associated equipment mass in kilograms, and a \"value rating\" that approximates how important to science the collected data will be. The following table lists the set E of all experiments: Unfortunately, not all of the experiments can be flown due to mass constraints - there\'s only 700 kg of payload available for the experiments. Launching stuff into orbit is expensive! Thus, the challenge is to pick the subset of E whose elements have the highest possible combined value rating but at the same time have a combined mass of 700 kg or less. One way to solve this problem is to use a \"brute force\" approach Consider ALL subsets of E. For each subset, determine its overall mass and value rating. Keep track of the highest-value subset with a combined mass of 700 or less. Once all the subsets are considered, this highest-value subset will be the one that you want to fly! Write a program that uses your function from # 1 and the brute force technique to find and display the optimal solution. Which experiments should be chosen? What is the total mass and value rating of the optimal solution9 Even though it works fine for this problem, why would this brute force approach be terribly inefficient if you had a large number of experiments?

Solution

Brute Force : Lets say we have n element in the table so total number of subsets 2^n. For each subset , to deteremine the total rating we have to traverse n times effectively hence time(n) = O(n x 2^n).

1) maxRating = -1

2) Loop over all the subsets and for each subset

   a) find the sum of all element from the subset and call it currentSum

   b) if (maxRating < currentSum) && (sumOfMassWeight <= MaxMassWeight) then maxRating = currentSum and mark the index of this subset as finalIndex else continue to the next Index of the subset

3) so the finalIndexed subset will be the subset with maximum rating and maxRating will be ans.

So better approach will be to use greedy approach : Basically this problem reduces to fractional knapsack problem where we have to maximize the value/weigh ratio

Idea : we will maximize rating/mass for the subset

struct Item

{

    int rating, mass;

    // Constructor

    Item(int rating, int mass) : rating(rating), mass(mass)

    {   // Constructor body}

};

bool cmp(struct Item a, struct Item b)

{

    double r1 = (double)a.value / a.weight;

    double r2 = (double)b.value / b.weight;

    return r1 > r2;

}

double FindMaxRatingSubset(int W, struct Item arr[], int n)
{
    //    sorting Item on basis of ratio
    sort(arr, arr + n, cmp);

    // see the new order
   
    for (int i = 0; i < n; i++)
    {
        cout << arr[i].rating<< \" \" << arr[i].mass << \" : \"
             << ((double)arr[i].rating / arr[i].mass) << endl;
    }
    
    int curWeight = 0; // Current weight in knapsack
    double finalvalue = 0.0; // Result (rating in Knapsack)

    // Looping through all Items
    for (int i = 0; i < n; i++)
    {
        // If adding Item won\'t overflow, add it completely
        if (curWeight + arr[i].mass<= W)
        {
            curWeight += arr[i].mass;
            finalvalue += arr[i].rating;
        }

        // If we can\'t add current Item, add fractional part of it
        else
        {
            int remain = W - curWeight;
            finalvalue += arr[i].rating* ((double) remain / arr[i].mass);
            break;
        }
    }

    // Returning final value
    return finalvalue;
}

This will run in O(nlogn) // sorting + O(n) // Loop over n elements hence

T(n) = O(nLogn)

If any doubt then please comment me in the section given below.