Dada una array arr[] que consta de N números enteros positivos que representan los pesos de N artículos y un número entero positivo D , la tarea es encontrar la capacidad mínima de peso de un barco (digamos K ) para enviar todos los pesos dentro de D días de modo que el pedido de pesos cargados en el barco está en el orden de los elementos de la array en arr[] y la cantidad total de peso cargado por barco cada día es K .
Ejemplos:
Entrada: arr[] = {1, 2, 1}, D = 2
Salida: 3
Explicación:
Considere el peso mínimo requerido por el barco como 3 , luego a continuación se muestra el orden de los pesos, de modo que todo el peso se puede enviar dentro de D( = 2) días:
Día 1: Enviar los pesos de los valores 1 y 2 el primer día como la suma de los pesos 1 + 2 = 3 (<= 3).
Día 2: envíe los pesos del valor 1 el segundo día como la suma de los pesos 1 (<= 3).
Considerando la cantidad de peso mínimo como 3, envía todo el peso dentro de D(= 2) días. Por lo tanto, imprime 3.Entrada: arr[] = {9, 8, 10}, D = 3
Salida: 10
Enfoque: El problema dado se puede resolver utilizando la técnica Greedy y la búsqueda binaria . Se puede observar la monotonicidad del problema de que si todos los paquetes se pueden enviar con éxito dentro de D días con capacidad K , entonces definitivamente se pueden enviar con cualquier capacidad mayor que K. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos ans como -1 para almacenar la capacidad mínima resultante del barco requerida.
- Inicialice dos variables, digamos s y e con el elemento máximo en la array dada y la suma total de la array, respectivamente, que denota los límites inferior y superior del espacio de búsqueda.
- Iterar hasta que el valor de s sea menor o igual a e y realizar los siguientes pasos:
- Inicialice una variable, digamos mid como (s + e)/2 .
- Verifique si es posible enviar todos los paquetes dentro de D días cuando la capacidad máxima permitida es media . Si se determina que es verdadero , actualice el valor de ans a mid y el valor de e a (mid – 1) .
- De lo contrario, actualice el valor de s a (mid + 1) .
- Después de completar los pasos anteriores, imprima el valor de ans como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if the weights can be delivered in D
// days or not
bool isValid(int weight[], int n, int D, int mx)
{
// Stores the count of days required to ship all the
// weights if the maximum capacity is mx
int st = 1;
int sum = 0;
// Traverse all the weights
for (int i = 0; i < n; i++) {
sum += weight[i];
// If total weight is more than the maximum capacity
if (sum > mx) {
st++;
sum = weight[i];
}
// If days are more than D, then return false
if (st > D)
return false;
}
// Return true for the days < D
return true;
}
// Function to find the least weight capacity of a boat to
// ship all the weights within D days
void shipWithinDays(int weight[], int D, int n)
{
// Stores the total weights to be shipped
int sum = 0;
// Find the sum of weights
for (int i = 0; i < n; i++)
sum += weight[i];
// Stores the maximum weight in the array that has to be
// shipped
int s = weight[0];
for (int i = 1; i < n; i++)
s = max(s, weight[i]);
// Store the ending value for the search space
int e = sum;
// Store the required result
int res = -1;
// Perform binary search
while (s <= e) {
// Store the middle value
int mid = s + (e - s) / 2;
// If mid can be shipped, then update the result and
// end value of the search space
if (isValid(weight, n, D, mid)) {
res = mid;
e = mid - 1;
}
// Search for minimum value in the right part
else
s = mid + 1;
}
// Print the result
cout << res;
}
// Driver Code
int main()
{
int weight[] = { 9, 8, 10 };
int D = 3;
int N = sizeof(weight) / sizeof(weight[0]);
shipWithinDays(weight, D, N);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C program for the above approach
#include <stdbool.h>
#include <stdio.h>
// Find maximum between two numbers.
int max(int num1, int num2)
{
return (num1 > num2) ? num1 : num2;
}
// Function to check if the weights can be delivered in D
// days or not
bool isValid(int weight[], int n, int D, int mx)
{
// Stores the count of days required to ship all the
// weights if the maximum capacity is mx
int st = 1;
int sum = 0;
// Traverse all the weights
for (int i = 0; i < n; i++) {
sum += weight[i];
// If total weight is more than the maximum capacity
if (sum > mx) {
st++;
sum = weight[i];
}
// If days are more than D, then return false
if (st > D)
return false;
}
// Return true for the days < D
return true;
}
// Function to find the least weight capacity of a boat to
// ship all the weights within D days
void shipWithinDays(int weight[], int D, int n)
{
// Stores the total weights to be shipped
int sum = 0;
// Find the sum of weights
for (int i = 0; i < n; i++)
sum += weight[i];
// Stores the maximum weight in the array that has to be
// shipped
int s = weight[0];
for (int i = 1; i < n; i++)
s = max(s, weight[i]);
// Store the ending value for the search space
int e = sum;
// Store the required result
int res = -1;
// Perform binary search
while (s <= e) {
// Store the middle value
int mid = s + (e - s) / 2;
// If mid can be shipped, then update the result and
// end value of the search space
if (isValid(weight, n, D, mid)) {
res = mid;
e = mid - 1;
}
// Search for minimum value in the right part
else
s = mid + 1;
}
// Print the result
printf("%d", res);
}
// Driver Code
int main()
{
int weight[] = { 9, 8, 10 };
int D = 3;
int N = sizeof(weight) / sizeof(weight[0]);
shipWithinDays(weight, D, N);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program for the above approach
import java.io.*;
class GFG {
// Function to check if the weights can be delivered in
// D days or not
static boolean isValid(int[] weight, int n, int D,
int mx)
{
// Stores the count of days required to ship all the
// weights if the maximum capacity is mx
int st = 1;
int sum = 0;
// Traverse all the weights
for (int i = 0; i < n; i++) {
sum += weight[i];
// If total weight is more than the maximum
// capacity
if (sum > mx) {
st++;
sum = weight[i];
}
// If days are more than D, then return false
if (st > D)
return false;
}
// Return true for the days < D
return true;
}
// Function to find the least weight capacity of a boat
// to ship all the weights within D days
static void shipWithinDays(int[] weight, int D, int n)
{
// Stores the total weights to be shipped
int sum = 0;
// Find the sum of weights
for (int i = 0; i < n; i++)
sum += weight[i];
// Stores the maximum weight in the array that has
// to be shipped
int s = weight[0];
for (int i = 1; i < n; i++) {
s = Math.max(s, weight[i]);
}
// Store the ending value for the search space
int e = sum;
// Store the required result
int res = -1;
// Perform binary search
while (s <= e) {
// Store the middle value
int mid = s + (e - s) / 2;
// If mid can be shipped, then update the result
// and end value of the search space
if (isValid(weight, n, D, mid)) {
res = mid;
e = mid - 1;
}
// Search for minimum value in the right part
else
s = mid + 1;
}
// Print the result
System.out.println(res);
}
// Driver Code
public static void main(String[] args)
{
int[] weight = { 9, 8, 10 };
int D = 3;
int N = weight.length;
shipWithinDays(weight, D, N);
}
}
// This code is contributed by Aditya Kumar (adityakumar129)
Python3
# Python3 program for the above approach # Function to check if the weights # can be delivered in D days or not def isValid(weight, n, D, mx): # Stores the count of days required # to ship all the weights if the # maximum capacity is mx st = 1 sum = 0 # Traverse all the weights for i in range(n): sum += weight[i] # If total weight is more than # the maximum capacity if (sum > mx): st += 1 sum = weight[i] # If days are more than D, # then return false if (st > D): return False # Return true for the days < D return True # Function to find the least weight # capacity of a boat to ship all the # weights within D days def shipWithinDays(weight, D, n): # Stores the total weights to # be shipped sum = 0 # Find the sum of weights for i in range(n): sum += weight[i] # Stores the maximum weight in the # array that has to be shipped s = weight[0] for i in range(1, n): s = max(s, weight[i]) # Store the ending value for # the search space e = sum # Store the required result res = -1 # Perform binary search while (s <= e): # Store the middle value mid = s + (e - s) // 2 # If mid can be shipped, then # update the result and end # value of the search space if (isValid(weight, n, D, mid)): res = mid e = mid - 1 # Search for minimum value # in the right part else: s = mid + 1 # Print the result print(res) # Driver Code if __name__ == '__main__': weight = [ 9, 8, 10 ] D = 3 N = len(weight) shipWithinDays(weight, D, N) # This code is contributed by ipg2016107
C#
// C# program for the above approach
using System;
class GFG{
// Function to check if the weights
// can be delivered in D days or not
static bool isValid(int[] weight, int n,
int D, int mx)
{
// Stores the count of days required
// to ship all the weights if the
// maximum capacity is mx
int st = 1;
int sum = 0;
// Traverse all the weights
for(int i = 0; i < n; i++)
{
sum += weight[i];
// If total weight is more than
// the maximum capacity
if (sum > mx)
{
st++;
sum = weight[i];
}
// If days are more than D,
// then return false
if (st > D)
return false;
}
// Return true for the days < D
return true;
}
// Function to find the least weight
// capacity of a boat to ship all the
// weights within D days
static void shipWithinDays(int[] weight, int D, int n)
{
// Stores the total weights to
// be shipped
int sum = 0;
// Find the sum of weights
for(int i = 0; i < n; i++)
sum += weight[i];
// Stores the maximum weight in the
// array that has to be shipped
int s = weight[0];
for(int i = 1; i < n; i++)
{
s = Math.Max(s, weight[i]);
}
// Store the ending value for
// the search space
int e = sum;
// Store the required result
int res = -1;
// Perform binary search
while (s <= e)
{
// Store the middle value
int mid = s + (e - s) / 2;
// If mid can be shipped, then
// update the result and end
// value of the search space
if (isValid(weight, n, D, mid))
{
res = mid;
e = mid - 1;
}
// Search for minimum value
// in the right part
else
s = mid + 1;
}
// Print the result
Console.WriteLine(res);
}
// Driver Code
public static void Main()
{
int[] weight = { 9, 8, 10 };
int D = 3;
int N = weight.Length;
shipWithinDays(weight, D, N);
}
}
// This code is contributed by ukasp
Javascript
<script>
// JavaScript program for the above approach
// Function to check if the weights
// can be delivered in D days or not
function isValid(weight, n,
D, mx)
{
// Stores the count of days required
// to ship all the weights if the
// maximum capacity is mx
let st = 1;
let sum = 0;
// Traverse all the weights
for(let i = 0; i < n; i++)
{
sum += weight[i];
// If total weight is more than
// the maximum capacity
if (sum > mx)
{
st++;
sum = weight[i];
}
// If days are more than D,
// then return false
if (st > D)
return false;
}
// Return true for the days < D
return true;
}
// Function to find the least weight
// capacity of a boat to ship all the
// weights within D days
function shipWithinDays(weight, D, n)
{
// Stores the total weights to
// be shipped
let sum = 0;
// Find the sum of weights
for(let i = 0; i < n; i++)
sum += weight[i];
// Stores the maximum weight in the
// array that has to be shipped
let s = weight[0];
for(let i = 1; i < n; i++)
{
s = Math.max(s, weight[i]);
}
// Store the ending value for
// the search space
let e = sum;
// Store the required result
let res = -1;
// Perform binary search
while (s <= e)
{
// Store the middle value
let mid = s + Math.floor((e - s) / 2);
// If mid can be shipped, then
// update the result and end
// value of the search space
if (isValid(weight, n, D, mid))
{
res = mid;
e = mid - 1;
}
// Search for minimum value
// in the right part
else
s = mid + 1;
}
// Print the result
document.write(res);
}
// Driver Code
let weight = [ 9, 8, 10 ];
let D = 3;
let N = weight.length;
shipWithinDays(weight, D, N);
</script>
Producción:
10
Complejidad de tiempo: O(N*log(S – M)), donde S es la suma de los elementos del arreglo y M es el elemento máximo del arreglo .
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por parthagarwal1962000 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA