Минимальное количество сумок равного количества, чтобы собрать не менее M денег

Опубликовано: 20 Января, 2022

Дано неограниченное количество монет двух номиналов 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

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

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>

Выход :

Сложность времени: O (N / X)
Автор статьи - Анудж Чаухан. Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Алгоритмы

Минимальное количество сумок равного количества, чтобы собрать не менее M денег

C++

Java

Python3

C#

PHP

Javascript

РЕКОМЕНДУЕМЫЕ СТАТЬИ