CODEWITHSUNDEEP
algorithmrecursiondynamic-programming
Sai Krishna Garlapati
Sai Krishna Garlapati

Reputation: 5

Get k integers such that the ratio of sums of lists is maximum

Given 2 arrays a and b of integers of length N, where a[i] denotes the area of the i'th building and b[i] denotes the price of the i'th building, select k buildings such that the sum of the prices of those buildings/sum of the areas of those buildings (ratio of total price to the total area) is maximum.

Could anybody suggest an approach to solve this problem? I got this in a test and was unable to solve it.

Upvotes: 0

Views: 167

Answers (1)

code_it
code_it

Reputation: 127

To solve this question recursion, When you are at ith index of your array, you could either select that building and consider its price and area for the final answer or you could just ignore this building and move to next index.

So whenever we choose any building increase area_till_now by area of current building and increase price_till_now by price of current building and decrease remaining_k by 1.

(0-based indexing)
double ans=0;
        
void recur(int current_index,double price_till_now,double area_till_now,int remaining_k){
     
    // we have selected k buildings.
    // so simply find the ratio and update maximum answer possible          
    if(remaining_k==0){
        double ratio=price_till_now/area_till_now;
        ans=max(ans,ratio);
        return;
    }
    // if we reach end of our array,
    // return as we cant select any more building
    if(current_index==n)return;

    // recur without selecting this building
    recur(current_index+1,price_till_now,area_till_now,left);

    // recur after selecting this building
    recur(current_index+1,price_till_now+price[current_index],area_till_now+area[current_index],left-1));
}

Since every building has either 2 choice for getting selected or not so it will have a O(2^n) time complexity.

Update: - My earlier dp solution had wrong calculations. Soon i'll update the optimized and correct dp solution.

Upvotes: 1

Related Questions