最低数量的同等数量的袋子，以收集至少百万美元-yiteyi-C++库

两种面额的硬币数量不限十、和 Y .还提供容量为 N 卢比，与硬币数量无关。任务是找到最少的行李数量，使每个行李包含相同数量的卢比，并且所有行李数量的总和至少为 M . 例如：

null

Input : M = 27, N = 12, X = 2, Y = 5. Output : 3We put 2 coins of X, 1 coin of Y in each bag. So we have 9 rupees in each bag and we need at least 3 bags (Note that 27/9 = 3). There is no way to obtain sum with lesser numberof bags.Input : M = 45, N = 9, X = 4, Y = 5. Output : 5

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

任务是最小化行李数量，因此需要最大化一个行李中的数量，以便所有行李中的数量相同。假设我们取X个硬币的“p”个数和Y个硬币的“q”个数，那么任务就是最大化p*X+q*Y，并且p*X+q*Y<=N。现在，为了找到方程左边的最大可能值，将p从0变为N/X，然后找到特定p的最大可能q。然后，从所有这些对中，取（p，q）对，它给出了p*X+q*Y的最大值。以下是上述理念的实施：

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）本文由 阿努伊·乔汉 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用贡献极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章