Минимальное количество сумок равного количества, чтобы собрать не менее M денег
Дано неограниченное количество монет двух номиналов X и Y. Также выдаются мешки вместимостью N рупий, независимо от количества монет. Задача состоит в том, чтобы найти минимальное количество сумок, чтобы в каждом из них было одинаковое количество рупий, а сумма всех сумок была не менее M.
Примеры :
Ввод: M = 27, N = 12, X = 2, Y = 5. Выход: 3 В каждый мешочек кладем по 2 монеты X, по 1 монете Y. Итак, у нас в каждой сумке по 9 рупий и нам нужно минимум 3 мешка (учтите, что 27/9 = 3). Там невозможно получить сумму с меньшим числом сумок. Ввод: M = 45, N = 9, X = 4, Y = 5. Выход: 5
The task is to minimize the number of bags, thus need to maximize the amount in a bag such that amount in all bags is same. Suppose we take, ‘p’ number of X coins and ‘q’ number of Y coins, then the task is to maximize p*X + q*Y. And also, p*X + q*Y <= N.
Now, to find the maximum possible value of Left Hand Side of the equation, vary p from 0 to N/X, then find the maximum possible q for the particular p. Then, out of all such pairs, take the (p, q) pair which gives maximum value of p*X + q*Y.
Below is the implementation of above idea :
C++
// C++ program to find minimum number of bags such // that each bag contains same amount and sum is at // least M. #include<bits/stdc++.h> using namespace std; // Return minimum number of bags required. int minBags( int M, int N, int X, int Y) { // Initialize maximum amount in a bag int maxAmount = 0; // Finding maximum possible q for the particular p. for ( int p = 0; p <= N/X; p++) { int q = (N - p * X) / Y; maxAmount = max(maxAmount, p*X + q*Y); } // Calculating the minimum number of bags. int result = M/maxAmount; result += (M % maxAmount == 0? 0: 1); return result; } // Driven Program int main() { int M = 45, N = 9; int X = 4, Y = 5; cout << minBags(M, N, X, Y) << endl; return 0; } |
Java
// Java program to find minimum number // of bags such that each bag contains // same amount and sum is at least M import java.io.*; public class GFG { // Return minimum number of bags required. static int minBags( int M, int N, int X, int Y) { // Initialize maximum amount in a bag int maxAmount = 0 ; // Finding maximum possible q // for the particular p. for ( int p = 0 ; p <= N / X; p++) { int q = (N - p * X) / Y; maxAmount = Math.max(maxAmount, p * X + q * Y); } // Calculating the minimum number of bags. int result = M / maxAmount; result += (M % maxAmount == 0 ? 0 : 1 ); return result; } // Driver Code static public void main (String[] args) { int M = 45 , N = 9 ; int X = 4 , Y = 5 ; System.out.println(minBags(M, N, X, Y)); } } // This code is contributed by vt_m. |
Python3
# Python 3 program to find minimum number # of bags such that each bag contains same # amount and sum is at least M. # Return minimum number of bags required. def minBags(M, N, X, Y): # Initialize maximum amount in a bag maxAmount = 0 # Finding maximum possible q for # the particular p. for p in range ( 0 , int (N / X) + 1 , 1 ): q = int ((N - p * X) / Y) maxAmount = max (maxAmount, p * X + q * Y) # Calculating the minimum number of bags. result = int (M / maxAmount) if (M % maxAmount = = 0 ): result + = 0 else : result + = 1 return result # Driver Code if __name__ = = "__main__" : M = 45 N = 9 X = 4 Y = 5 print (minBags(M, N, X, Y)) # This code is contributed by # Surendra_Gangwar |
C#
// C# program to find minimum number of // bags such that each bag contains same // amount and sum is at least M. using System; public class GFG { // Return minimum number of bags required. static int minBags( int M, int N, int X, int Y) { // Initialize maximum amount in a bag int maxAmount = 0; // Finding maximum possible q // for the particular p. for ( int p = 0; p <= N / X; p++) { int q = (N - p * X) / Y; maxAmount = Math.Max(maxAmount, p * X + q * Y); } // Calculating the minimum number of bags. int result = M / maxAmount; result += (M % maxAmount == 0? 0: 1); return result; } // Driver Code static public void Main () { int M = 45, N = 9; int X = 4, Y = 5; Console.WriteLine(minBags(M, N, X, Y)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program to find minimum // number of bags such that each // bag contains same amount and // sum is at least M. // Return minimum number // of bags required. function minBags( $M , $N , $X , $Y ) { // Initialize maximum // amount in a bag $maxAmount = 0; // Finding maximum possible // q for the particular p. for ( $p = 0; $p <= $N / $X ; $p ++) { $q = ( $N - $p * $X ) / $Y ; $maxAmount = max( $maxAmount , $p * $X + $q * $Y ); } // Calculating the minimum // number of bags. $result = $M / $maxAmount ; $result += ( $M % $maxAmount == 0? 0: 1); return $result ; } // Driver Code $M = 45; $N = 9; $X = 4 ; $Y = 5; echo minBags( $M , $N , $X , $Y ) ; // This code is contributed by nitin mittal. ?> |
Javascript
<script> // Javascript program to find minimum number // of bags such that each bag contains // same amount and sum is at least M // Return minimum number of bags required. function minBags(M, N, X, Y) { // Initialize maximum amount in a bag let maxAmount = 0; // Finding maximum possible q // for the particular p. for (let p = 0; p <= N / X; p++) { let q = (N - p * X) / Y; maxAmount = Math.max(maxAmount, p * X + q * Y); } // Calculating the minimum number of bags. let result = M / maxAmount; result += (M % maxAmount == 0? 0: 1); return result; } // Driver code let M = 45, N = 9; let X = 4, Y = 5; document.write(minBags(M, N, X, Y)); // This code is contributed by susmitakundugoaldanga. </script> |
Выход :
5
Сложность времени: O (N / X)
Автор статьи - Анудж Чаухан. Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.