Horje
Maximize sum of ratios of N given fractions by incrementing numerator and denominators K times by 1

Given a positive integer K and an array arr[] consisting of {numerator, denominator} of N fractions, the task is to find the sum of the ratio of the given fractions after incrementing numerators and denominators by 1, K number of times.

Examples:

Input: arr[][] = {{1, 2}, {3, 5}, {2, 2}}, K = 2
Output: 0.78333
Explanation:
The most optimal choice is to increment the first fraction K(= 2) number of times. Therefore, the sum of ratio is (3/4 + 3/5 + 2/2) / 3 = 0.78333, which is maximum possible.

Input: arr[][] = {{1, 1}, {4, 5}}, K = 5
Output: 0.95

 

Approach: The given problem can be solved by using the Greedy Approach, the idea is to increment that fraction among the given fractions whose increment maximizes the sum of ratios of fractions. This idea can be implemented using the priority queue. Follow the below steps to solve the problem:

  • Initialize a Max Heap, say PQ using the priority queue which stores the value that will be incremented in the total average ratio if an operation is performed on ith index for all values of i in the range [0, N).
  • Insert all the indexes of the fraction in the array arr[] in the priority queue PQ with the incremented value of fractions.
  • Iterate over the range [0, K – 1] and perform the following steps:
    • Pop the top element of the PQ.
    • Increment the fraction of the current popped index.
    • Insert all the current fractions in the array arr[] in the priority queue PQ with the incremented value of fractions.
  • After completing the above steps, print the sum of ratios of all the fractions stored in priority_queue PQ.

Below is the implementation of the above approach: 

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to increment the K fractions
// from the given array to maximize the
// sum of ratios of the given fractions
double maxAverageRatio(
    vector<vector<int> >& arr, int K)
{
    // Size of the array
    int N = arr.size();
 
    // Max priority queue
    priority_queue<pair<double, int> > q;
 
    // Iterate through the array
    for (int i = 0; i < N; i++) {
 
        // Insert the incremented value
        // if an operation is performed
        // on the ith index
        double extra
            = (((double)arr[i][0] + 1)
               / ((double)arr[i][1] + 1))
              - ((double)arr[i][0]
                 / (double)arr[i][1]);
        q.push(make_pair(extra, i));
    }
 
    // Loop to perform K operations
    while (K--) {
        int i = q.top().second;
        q.pop();
 
        // Increment the numerator and
        // denominator of ith fraction
        arr[i][0] += 1;
        arr[i][1] += 1;
 
        // Add the incremented value
        double extra
            = (((double)arr[i][0] + 1)
               / ((double)arr[i][1] + 1))
              - ((double)arr[i][0]
                 / (double)arr[i][1]);
 
        q.push(make_pair(extra, i));
    }
 
    // Stores the average ratio
    double ans = 0;
    for (int i = 0; i < N; i++) {
        ans += ((double)arr[i][0]
                / (double)arr[i][1]);
    }
 
    // Return the ratio
    return ans / N;
}
 
// Driver Code
int main()
{
    vector<vector<int> > arr
        = { { 1, 2 }, { 3, 5 }, { 2, 2 } };
    int K = 2;
 
    cout << maxAverageRatio(arr, K);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class Pair<K, V> {
  private final K key;
  private final V value;
 
  public Pair(K key, V value)
  {
    this.key = key;
    this.value = value;
  }
 
  public K getKey() { return key; }
 
  public V getValue() { return value; }
}
 
class GFG {
 
  // Function to increment the K fractions
  // from the given array to maximize the
  // sum of ratios of the given fractions
  static double maxAverageRatio(int[][] arr, int K)
  {
    // Size of the array
    int N = arr.length;
 
    // Max priority queue
    PriorityQueue<Pair<Double, Integer> > q
      = new PriorityQueue<>(
      new Comparator<Pair<Double, Integer> >() {
        @Override
        public int compare(
          Pair<Double, Integer> a,
          Pair<Double, Integer> b)
        {
          return b.getKey().compareTo(
            a.getKey());
        }
      });
 
    // Iterate through the array
    for (int i = 0; i < N; i++) {
      // Insert the incremented value
      // if an operation is performed
      // on the ith index
      double extra
        = (((double)arr[i][0] + 1)
           / ((double)arr[i][1] + 1))
        - ((double)arr[i][0] / (double)arr[i][1]);
      q.offer(new Pair<>(extra, i));
    }
 
    // Loop to perform K operations
    while (K-- > 0) {
      int i = q.poll().getValue();
 
      // Increment the numerator and
      // denominator of ith fraction
      arr[i][0] += 1;
      arr[i][1] += 1;
 
      // Add the incremented value
      double extra
        = (((double)arr[i][0] + 1)
           / ((double)arr[i][1] + 1))
        - ((double)arr[i][0] / (double)arr[i][1]);
      q.offer(new Pair<>(extra, i));
    }
 
    // Stores the average ratio
    double ans = 0;
    for (int i = 0; i < N; i++) {
      ans += ((double)arr[i][0] / (double)arr[i][1]);
    }
 
    // Return the ratio
    return ans / N;
  }
 
  public static void main(String[] args)
  {
    int[][] arr = { { 1, 2 }, { 3, 5 }, { 2, 2 } };
    int K = 2;
 
    System.out.printf("%.6f", maxAverageRatio(arr, K));
  }
}
 
// This code is contributed by lokesh.

Python3

# Python program for the above approach
 
# Function to increment the K fractions
# from the given array to maximize the
# sum of ratios of the given fractions
def maxAverageRatio(arr,k):
     
    #Size of the array
    N=len(arr)
     
    # Max priority queue
    q=[]
     
    # Iterate through the array
    for i in range(N):
        # Insert the incremented value
        # if an operation is performed
        # on the ith index
        extra = ((float(arr[i][0])+1)/(float(arr[i][1])+1))-(float(arr[i][0])/float(arr[i][1]))
        q.append([extra,i])
         
    # Loop to perform K operations
    while(k>0):
        k=k-1
         
        i=q[0][1]
        q.pop(0)
        # Increment the numerator and
        # denominator of ith fraction
        arr[i][0]=arr[i][0]+1
        arr[i][1]=arr[i][1]+1
        # Add the incremented value
        extra = ((float(arr[i][0])+1)/(float(arr[i][1])+1))-(float(arr[i][0])/float(arr[i][1]))
        q.append([extra,i])
     
    # Stores the average ratio
    ans=0
    for i in range(N):
        ans=ans+(float(arr[i][0])/float(arr[i][1]))
     
    # Return the ratio
    return ans/N
 
# Driver Code
 
arr = [ [ 1, 2 ], [ 3, 5 ], [ 2, 2 ] ]
K = 2
 
print(maxAverageRatio(arr, K))
 
# This code is contributed by Pushpesh Raj

C#

// C# program for the above approach
using System;
using System.Linq;
using System.Collections.Generic;
 
class GFG
{
   
  // Structure to store a fraction
  private struct Fraction
  {
    public int Numerator;
    public int Denominator;
  }
 
  // Function to increment the K fractions
  // from the given array to maximize the
  // sum of ratios of the given fractions
  static double MaxAverageRatio(Fraction[] arr, int K)
  {
    // Size of the array
    int N = arr.Length;
 
    // Array to store extra value after incrementing
    // each fraction
    double[] extra = new double[N];
 
    // Iterate through the array
    for (int i = 0; i < N; i++) {
      // Calculate extra value after incrementing
      // fraction
      extra[i] = ((double)(arr[i].Numerator + 1)
                  / (double)(arr[i].Denominator + 1))
        - (double)arr[i].Numerator
        / (double)arr[i].Denominator;
    }
 
    // Loop to perform K operations
    while (K-- > 0) {
      // Find the index of fraction with the maximum
      // extra value
      int index = Array.IndexOf(extra, extra.Max());
 
      // Increment the numerator and denominator of
      // fraction
      arr[index].Numerator += 1;
      arr[index].Denominator += 1;
 
      // Calculate new extra value for the fraction
      extra[index]
        = ((double)(arr[index].Numerator + 1)
           / (double)(arr[index].Denominator + 1))
        - (double)arr[index].Numerator
        / (double)arr[index].Denominator;
    }
 
    // Stores the average ratio
    double ans = 0;
    for (int i = 0; i < N; i++) {
      ans += (double)arr[i].Numerator
        / (double)arr[i].Denominator;
    }
 
    // Return the ratio
    return ans / N;
  }
 
  static void Main(string[] args)
  {
    Fraction[] arr = new Fraction[] {
      new Fraction{ Numerator = 1, Denominator = 2 },
      new Fraction{ Numerator = 3, Denominator = 5 },
      new Fraction{ Numerator = 2, Denominator = 2 }
    };
    int K = 2;
 
    Console.WriteLine("{0:0.000000}",
                      MaxAverageRatio(arr, K));
  }
}
 
// This code is contributed by phasing17.

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to increment the K fractions
// from the given array to maximize the
// sum of ratios of the given fractions
function maxAverageRatio(arr, K)
{
 
    // Size of the array
    var N = arr.length;
 
    // Max priority queue
    var q = [];
 
    // Iterate through the array
    for (var i = 0; i < N; i++) {
 
        // Insert the incremented value
        // if an operation is performed
        // on the ith index
        var extra
            = ((arr[i][0] + 1)
               / (arr[i][1] + 1))
              - (arr[i][0]
                 / arr[i][1]);
        q.push([extra, i]);
    }
    q.sort();
    // Loop to perform K operations
    while (K--) {
        var i = q[q.length-1][1];
        q.pop();
 
        // Increment the numerator and
        // denominator of ith fraction
        arr[i][0] += 1;
        arr[i][1] += 1;
 
        // Add the incremented value
        var extra
            = ((arr[i][0] + 1)
               / (arr[i][1] + 1))
              - (arr[i][0]
                 / arr[i][1]);
 
        q.push([extra, i]);
        q.sort();
    }
 
    // Stores the average ratio
    var ans = 0;
    for (var i = 0; i < N; i++) {
        ans += (arr[i][0]
                / arr[i][1]);
    }
 
    // Return the ratio
    return ans / N;
}
 
// Driver Code
var arr = [[1, 2 ], [3, 5], [2, 2 ]];
var K = 2;
document.write(maxAverageRatio(arr, K).toFixed(6));
 
// This code is contributed by rrrtnx.
</script>

Output: 

0.783333

 

Time Complexity: O(K*log N)
Auxiliary Space: O(N)


 


Reffered: https://www.geeksforgeeks.org

Greedy

Related
Maximum length of consecutive 1s or 0s after flipping at most K characters Maximum length of consecutive 1s or 0s after flipping at most K characters
Find Minimum Number Of Arrows Needed To Burst All Balloons Find Minimum Number Of Arrows Needed To Burst All Balloons
Minimize value of |A - X| + |B - Y| + |C - Z| such that X * Y = Z Minimize value of |A - X| + |B - Y| + |C - Z| such that X * Y = Z
Koko Eating Bananas Koko Eating Bananas
Why does Dijkstra&#039;s Algorithm fail on negative weights? Why does Dijkstra&#039;s Algorithm fail on negative weights?

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 11



 

Horje