Минимальное количество предметов для доставки

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

Дано N корзин, каждая из которых содержит A [i] элементов. Учитывая K туров, в рамках которых необходимо доставить все предметы. За 1 тур разрешено брать предметы только из одного ведра. Задача состоит в том, чтобы указать минимальное количество предметов, которое необходимо доставить за тур, чтобы все предметы можно было доставить в рамках K туров.
Условия: K> = N
Примеры :

 Вход : 
N = 5
A [] = {1, 3, 5, 7, 9}
К = 10
Выход : 3
Доставляя 3 предмета за раз, 
Количество обходов, необходимых для ведра 1 = 1
Количество обходов, необходимых для ведра 2 = 1
Количество обходов, необходимых для ведра 3 = 2
Количество обходов, необходимых для ведра 4 = 3
Количество обходов, необходимых для ведра 5 = 3
Общее количество туров = 10

Вход :
N = 10
А = 1, 4, 9, 16, 25, 36, 49, 64, 81, 100
к = 50
Выход : 9

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

Approach: It is needed to find the minimum number of items per delivery. So, the idea is to iterate from 1 to the maximum value of items in a bucket and calculate the number of tours required for each bucket and find the total number of tours for complete delivery. The first such value with tours less than or equals K gives the required number.
Below is the implementation of the above idea:

C++

//C++ program to find the minimum numbers of tours required
#include <bits/stdc++.h>
 
using namespace std;
int getMin(int N,int A[],int k)
{
    //Iterating through each possible
   // value of minimum Items
   int maximum=0,tours=0;
    
   for(int i=0;i<N;i++)
       maximum=max(maximum,A[i]);
        
   for(int i=1;i<maximum+1;i++)
   {
       tours=0;
       for(int j=0;j<N;j++)
       {
           if(A[j]%i==0)//perfecctly Divisible
           {
               tours+=A[j]/i;
           }else{
                // Not Perfectly Divisible means required
                // tours are Floor Division + 1
                tours += floor(A[j]/i) + 1;
           }
       }
       if(tours<=k)
       {
             // Return First Feasible Value found,
            // since it is also the minimum
            return i;
       }
   }
    
   return -1;
}
//Driver code
int main()
{
  int a[]={1, 4, 9, 16, 25, 36, 49, 64, 81, 100};
   
  int n=sizeof(a)/sizeof(a[0]);
   
  int k=50;
   
  if(getMin(n,a,k)==-1)
   cout<<"Not Possible";
   else
   cout<<getMin(n,a,k);
   
}
//This code is contributed by Mohit kumar 29

Java

// Java program to find the minimum numbers of tours required
import java.util.*;
class solution
{
 
static int getMin(int N,int A[],int k)
{
    //Iterating through each possible
// value of minimum Items
int maximum=0,tours=0;
     
for(int i=0;i<N;i++)
    maximum=Math.max(maximum,A[i]);
         
for(int i=1;i<maximum+1;i++)
{
    tours=0;
    for(int j=0;j<N;j++)
    {
        if(A[j]%i==0)//perfecctly Divisible
        {
            tours+=A[j]/i;
        }else{
                // Not Perfectly Divisible means required
                // tours are Floor Division + 1
                tours += Math.floor(A[j]/i) + 1;
        }
    }
    if(tours<=k)
    {
            // Return First Feasible Value found,
            // since it is also the minimum
            return i;
    }
}
     
return -1;
}
//Driver code
public static void main(String args[])
{
int a[]={1, 4, 9, 16, 25, 36, 49, 64, 81, 100};
 
int n=a.length;
 
int k=50;
 
if(getMin(n,a,k)==-1)
System.out.println("Not Possible");
else
System.out.println(getMin(n,a,k));
 
}
}
//This code is contributed by
// Surendra_Gangwar

Python3

# Python3 program to find minimum numbers of
# tours required
 
def getMin(N, A, k):
 
    # Iterating through each possible
    # value of minimum Items
    for i in range(1, max(A)+1):
        tours = 0
        for j in range(0, len(A)):
            if(A[j]% i == 0):# Perfectly Divisible
                tours += A[j]/i
 
            else:
                # Not Perfectly Divisible means required
                # tours are Floor Division + 1
                tours += A[j]//i + 1
 
        if(tours <= k):
            # Return First Feasible Value found,
            # since it is also the minimum
            return i
    return "Not Possible"
 
# Driver Code
N = 10
A = [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
k = 50
print(getMin(N, A, k))

C#

// C# program to find the minimum
// numbers of tours required
using System;
 
class GFG
{
 
static int getMin(int N, int [] A, int k)
{
    // Iterating through each possible
    // value of minimum Items
    int maximum = 0,tours = 0;
     
    for(int i = 0; i < N; i++)
        maximum = Math.Max(maximum, A[i]);
         
    for(int i = 1; i < maximum + 1; i++)
    {
        tours = 0;
        for(int j = 0; j < N; j++)
        {
            if(A[j] % i == 0)// perfecctly Divisible
        {
            tours += A[j] /i;
        }
        else
        {
                // Not Perfectly Divisible means required
                // tours are Floor Division + 1
                tours += (int)Math.Floor(A[j] / (i * 1.0)) + 1;
        }
    }
        if(tours <= k)
        {
            // Return First Feasible Value found,
            // since it is also the minimum
            return i;
        }
    }
     
    return -1;
}
 
// Driver code
public static void Main()
{
    int []a = {1, 4, 9, 16, 25, 36, 49, 64, 81, 100};
 
    int n = 10;
 
    int k = 50;
 
    if(getMin(n, a, k) == -1)
        Console.WriteLine("Not Possible");
    else
        Console.WriteLine(getMin(n, a, k));
}
}
 
// This code is contributed by
// Mohit kumar

PHP

<?php
// PHP program to find the minimum number
// of tours required
 
function getMin($N, $A, $k)
{
     
    // Iterating through each possible
    // value of minimum Items
    $maximum = 0;
    $tours = 0;
         
    for($i = 0; $i < $N; $i++)
        $maximum = max($maximum, $A[$i]);
             
    for($i = 1; $i < $maximum + 1; $i++)
    {
        $tours = 0;
        for($j = 0; $j < $N; $j++)
        {
            if($A[$j] % $i == 0) // perfectly Divisible
            {
                $tours += $A[$j] / $i;
            }
            else
            {
                // Not Perfectly Divisible means required
                // tours are Floor Division + 1
                $tours += floor($A[$j] / $i) + 1;
            }
        }
         
        if($tours <= $k)
        {
            // Return First Feasible Value found,
            // since it is also the minimum
            return $i;
        }
    }
         
    return -1;
}
 
// Driver code
$a = array(1, 4, 9, 16, 25, 36,
               49, 64, 81, 100);
 
$n = sizeof($a);
 
$k = 50;
 
if(getMin($n, $a, $k) == -1)
    echo "Not Possible";
else
    echo getMin($n, $a, $k);
 
// This code is contributed by ihritik
?>

Javascript

<script>
// Javascript program to find the minimum numbers of tours required
     
function getMin(N,A,k)
{
    //Iterating through each possible
// value of minimum Items
let maximum = 0, tours = 0;
       
for(let i = 0; i < N; i++)
    maximum=Math.max(maximum, A[i]);
           
for(let i = 1; i < maximum + 1; i++)
{
    tours = 0;
    for(let j = 0; j < N; j++)
    {
        if(A[j] % i == 0)//perfecctly Divisible
        {
            tours+=Math.floor(A[j]/i);
        }else{
                // Not Perfectly Divisible means required
                // tours are Floor Division + 1
                tours += Math.floor(A[j]/i) + 1;
        }
    }
    if(tours<=k)
    {
            // Return First Feasible Value found,
            // since it is also the minimum
            return i;
    }
}
       
return -1;
}
 
//Driver code
let a = [1, 4, 9, 16, 25, 36, 49, 64, 81, 100];
let n = a.length;
let k = 50;
 
if(getMin(n, a, k) == -1)
    document.write("Not Possible<br>");
else
    document.write(getMin(n, a, k));   
 
// This code is contributed by patel2127
</script>

Output:

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

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

Алгоритмы Picked

Минимальное количество предметов для доставки

C++

Java

Python3

C#

PHP

Javascript

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