El problema de la partición del pintor | conjunto 2

Tenemos que pintar n tableros de longitud {A1, A2, .. An}. Hay k pintores disponibles y cada uno tarda 1 unidad de tiempo en pintar 1 unidad de tabla. El problema es encontrar el tiempo mínimo para realizar este trabajo bajo las restricciones de que cualquier pintor solo pintará secciones continuas de tableros, digamos el tablero {2, 3, 4} o solo el tablero {1} o nada pero no el tablero {2, 4, 5}.

Ejemplos: 

Input : k = 2, A = {10, 10, 10, 10} 
Output : 20.
Here we can divide the boards into 2
equal sized partitions, so each painter 
gets 20 units of board and the total
time taken is 20. 

Input : k = 2, A = {10, 20, 30, 40} 
Output : 60.
Here we can divide first 3 boards for
one painter and the last board for 
second painter.

En la publicación anterior discutimos un enfoque basado en programación dinámica que tiene complejidad de tiempo  y  espacio adicional. 
En esta publicación, analizaremos un enfoque más eficiente utilizando la búsqueda binaria. Sabemos que el invariante de la búsqueda binaria tiene dos partes principales: 
* el valor objetivo siempre estaría en el rango de búsqueda. 
* el rango de búsqueda disminuirá en cada ciclo para que se pueda llegar a la terminación. 

También sabemos que los valores en este rango deben estar ordenados. Aquí nuestro valor objetivo es la suma máxima de una sección contigua en la asignación óptima de tableros. Ahora, ¿cómo podemos aplicar la búsqueda binaria para esto? Podemos fijar el posible rango bajo a alto para el valor objetivo y reducir nuestra búsqueda para obtener la asignación óptima.

Podemos ver que el valor más alto posible en este rango es la suma de todos los elementos de la array y esto sucede cuando asignamos 1 pintor a todas las secciones del tablero. El valor más bajo posible de este rango es el valor máximo de la array max, ya que en esta asignación podemos asignar max a un pintor y dividir las otras secciones de manera que el costo de ellas sea menor o igual a max y lo más cerca posible a máx. Ahora, si consideramos que usamos x pintores en los escenarios anteriores, es obvio que a medida que aumenta el valor en el rango, el valor de x disminuye y viceversa. A partir de esto, podemos encontrar el valor objetivo cuando x=k y usar una función de ayuda para encontrar x, el número mínimo de pintores requeridos cuando se da la longitud máxima de la sección que un pintor puede pintar.

// CPP program for painter's partition problem
#include <iostream>
#include <climits>
using namespace std;
 
// return the maximum element from the array
int getMax(int arr[], int n)
{
    int max = INT_MIN;
    for (int i = 0; i < n; i++)
        if (arr[i] > max)
            max = arr[i];
    return max;
}
 
// return the sum of the elements in the array
int getSum(int arr[], int n)
{
    int total = 0;
    for (int i = 0; i < n; i++)
        total += arr[i];
    return total;
}
 
// find minimum required painters for given maxlen
// which is the maximum length a painter can paint
int numberOfPainters(int arr[], int n, int maxLen)
{
    int total = 0, numPainters = 1;
 
    for (int i = 0; i < n; i++) {
        total += arr[i];
 
        if (total > maxLen) {
 
            // for next count
            total = arr[i];
            numPainters++;
        }
    }
 
    return numPainters;
}
 
int partition(int arr[], int n, int k)
{
    int lo = getMax(arr, n);
    int hi = getSum(arr, n);
 
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        int requiredPainters = numberOfPainters(arr, n, mid);
 
        // find better optimum in lower half
        // here mid is included because we
        // may not get anything better
        if (requiredPainters <= k)
            hi = mid;
 
        // find better optimum in upper half
        // here mid is excluded because it gives
        // required Painters > k, which is invalid
        else
            lo = mid + 1;
    }
 
    // required
    return lo;
}
 
// driver function
int main()
{
    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    cout << partition(arr, n, k) << endl;
    return 0;
}

// Java Program for painter's partition problem
import java.util.*;
import java.io.*;
 
class GFG {
    // return the maximum element from the array
    static int getMax(int arr[], int n)
    {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++)
            if (arr[i] > max)
                max = arr[i];
        return max;
    }
 
    // return the sum of the elements in the array
    static int getSum(int arr[], int n)
    {
        int total = 0;
        for (int i = 0; i < n; i++)
            total += arr[i];
        return total;
    }
 
    // find minimum required painters for given maxlen
    // which is the maximum length a painter can paint
    static int numberOfPainters(int arr[], int n, int maxLen)
    {
        int total = 0, numPainters = 1;
 
        for (int i = 0; i < n; i++) {
            total += arr[i];
 
            if (total > maxLen) {
 
                // for next count
                total = arr[i];
                numPainters++;
            }
        }
 
        return numPainters;
    }
 
    static int partition(int arr[], int n, int k)
    {
        int lo = getMax(arr, n);
        int hi = getSum(arr, n);
 
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            int requiredPainters = numberOfPainters(arr, n, mid);
 
            // find better optimum in lower half
            // here mid is included because we
            // may not get anything better
            if (requiredPainters <= k)
                hi = mid;
 
            // find better optimum in upper half
            // here mid is excluded because it gives
            // required Painters > k, which is invalid
            else
                lo = mid + 1;
        }
 
        // required
        return lo;
    }
 
    // Driver code
    public static void main(String args[])
    {
        int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 
        // Calculate size of array.
        int n = arr.length;
        int k = 3;
        System.out.println(partition(arr, n, k));
    }
}
 
// This code is contributed by Sahil_Bansall

# Python program for painter's partition problem
 
# Find minimum required painters for given maxlen
# which is the maximum length a painter can paint
def numberOfPainters(arr, n, maxLen):
    total = 0
    numPainters = 1
 
    for i in arr:
        total += i
 
        if (total > maxLen):
 
            # for next count
            total = i
            numPainters += 1
 
    return numPainters
 
def partition(arr, n, k):
    lo = max(arr)
    hi = sum(arr)
 
    while (lo < hi):
        mid = lo + (hi - lo) // 2
        requiredPainters = numberOfPainters(arr, n, mid)
 
        # find better optimum in lower half
        # here mid is included because we
        # may not get anything better
        if (requiredPainters <= k):
            hi = mid
 
        # find better optimum in upper half
        # here mid is excluded because it gives
        # required Painters > k, which is invalid
        else:
            lo = mid + 1
 
    # required
    return lo
 
# Driver code
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
n = len(arr)
k = 3
print(int(partition(arr, n, k)))

// C# Program for painter's
// partition problem
using System;
 
class GFG {
 
    // return the maximum
    // element from the array
    static int getMax(int[] arr, int n)
    {
        int max = int.MinValue;
        for (int i = 0; i < n; i++)
            if (arr[i] > max)
                max = arr[i];
        return max;
    }
 
    // return the sum of the
    // elements in the array
    static int getSum(int[] arr, int n)
    {
        int total = 0;
        for (int i = 0; i < n; i++)
            total += arr[i];
        return total;
    }
 
    // find minimum required
    // painters for given
    // maxlen which is the
    // maximum length a painter
    // can paint
    static int numberOfPainters(int[] arr,
                                int n, int maxLen)
    {
        int total = 0, numPainters = 1;
 
        for (int i = 0; i < n; i++) {
            total += arr[i];
 
            if (total > maxLen) {
 
                // for next count
                total = arr[i];
                numPainters++;
            }
        }
 
        return numPainters;
    }
 
    static int partition(int[] arr,
                         int n, int k)
    {
        int lo = getMax(arr, n);
        int hi = getSum(arr, n);
 
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            int requiredPainters = numberOfPainters(arr, n, mid);
 
            // find better optimum in lower
            // half here mid is included
            // because we may not get
            // anything better
            if (requiredPainters <= k)
                hi = mid;
 
            // find better optimum in upper
            // half here mid is excluded
            // because it gives required
            // Painters > k, which is invalid
            else
                lo = mid + 1;
        }
 
        // required
        return lo;
    }
 
    // Driver code
    static public void Main()
    {
        int[] arr = { 1, 2, 3, 4, 5,
                      6, 7, 8, 9 };
 
        // Calculate size of array.
        int n = arr.Length;
        int k = 3;
        Console.WriteLine(partition(arr, n, k));
    }
}
 
// This code is contributed by ajit

<?php
// PHP program for painter's
// partition problem
 
// return the maximum
// element from the array
function getMax($arr, $n)
{
    $max = PHP_INT_MIN;
    for ($i = 0; $i < $n; $i++)
        if ($arr[$i] > $max)
            $max = $arr[$i];
    return $max;
}
 
// return the sum of the
// elements in the array
function getSum($arr, $n)
{
    $total = 0;
    for ($i = 0; $i < $n; $i++)
        $total += $arr[$i];
    return $total;
}
 
// find minimum required painters
// for given maxlen which is the
// maximum length a painter can paint
function numberOfPainters($arr, $n,
                          $maxLen)
{
    $total = 0; $numPainters = 1;
 
    for ($i = 0; $i < $n; $i++)
    {
        $total += $arr[$i];
 
        if ($total > $maxLen)
        {
 
            // for next count
            $total = $arr[$i];
            $numPainters++;
        }
    }
 
    return $numPainters;
}
 
function partition($arr, $n, $k)
{
    $lo = getMax($arr, $n);
    $hi = getSum($arr, $n);
 
    while ($lo < $hi)
    {
        $mid = $lo + ($hi - $lo) / 2;
        $requiredPainters =
                    numberOfPainters($arr,
                                     $n, $mid);
 
        // find better optimum in
        // lower half here mid is
        // included because we may
        // not get anything better
        if ($requiredPainters <= $k)
            $hi = $mid;
 
        // find better optimum in
        // upper half here mid is
        // excluded because it
        // gives required Painters > k,
        // which is invalid
        else
            $lo = $mid + 1;
    }
 
    // required
    return floor($lo);
}
 
// Driver Code
$arr = array(1, 2, 3,
             4, 5, 6,
             7, 8, 9);
$n = sizeof($arr);
$k = 3;
 
echo partition($arr, $n, $k), "\n";
 
// This code is contributed by ajit
?>

<script>
 
// Javascript Program for painter's partition problem
    
// Return the maximum element from the array
function getMax(arr, n)
{
    let max = Number.MIN_VALUE;
    for(let i = 0; i < n; i++)
        if (arr[i] > max)
            max = arr[i];
             
    return max;
}
 
// Return the sum of the elements in the array
function getSum(arr, n)
{
    let total = 0;
    for(let i = 0; i < n; i++)
        total += arr[i];
         
    return total;
}
 
// Find minimum required paleters for given maxlen
// which is the maximum length a paleter can palet
function numberOfPaleters(arr, n, maxLen)
{
    let total = 0, numPaleters = 1;
 
    for(let i = 0; i < n; i++)
    {
        total += arr[i];
 
        if (total > maxLen)
        {
 
            // For next count
            total = arr[i];
            numPaleters++;
        }
    }
    return numPaleters;
}
 
function partition(arr, n, k)
{
    let lo = getMax(arr, n);
    let hi = getSum(arr, n);
 
    while (lo < hi)
    {
        let mid = lo + (hi - lo) / 2;
        let requiredPaleters = numberOfPaleters(
            arr, n, mid);
 
        // Find better optimum in lower half
        // here mid is included because we
        // may not get anything better
        if (requiredPaleters <= k)
            hi = mid;
 
        // find better optimum in upper half
        // here mid is excluded because it gives
        // required Paleters > k, which is invalid
        else
            lo = mid + 1;
    }
 
    // Required
    return lo;
}
 
// Driver code
let arr = [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ];
 
// Calculate size of array.
let n = arr.length;
let k = 3;
 
document.write(Math.round(partition(arr, n, k)));
 
// This code is contributed by sanjoy_62
 
</script>

Producción : 

17

Para una mejor comprensión, calque el ejemplo dado en el programa con lápiz y papel. 
La complejidad temporal del enfoque anterior es  .
Referencias: 
https://articles.leetcode.com/the-painters-partition-problem-part-ii/  
https://www.topcoder.com/community/data-science/data-science-tutorials/binary-search/
Preguntado en: Google, Codenation.