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 del tablero. 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 tablero {2, 3, 4} o solo tablero {1} o nada pero no tablero {2 , 4, 5}.
Ejemplos:
Entrada: k = 2, A = {10, 10, 10, 10}
Salida: 20
Explicación: Aquí podemos dividir los tableros en 2 particiones de igual tamaño, por lo que cada pintor obtiene 20 unidades de tablero y el tiempo total empleado es 20.Entrada: k = 2, A = {10, 20, 30, 40}
Salida: 60
Explicación: Aquí podemos dividir las primeras 3 tablas para un pintor y la última tabla para el segundo pintor.
De los ejemplos anteriores, es obvio que la estrategia de dividir los tableros en k particiones iguales no funcionará para todos los casos. Podemos observar que el problema se puede descomponer en: Dado un arreglo A de enteros no negativos y un entero positivo k, tenemos que dividir A en k de menos particiones tales que la suma máxima de los elementos en una partición, en general las particiones se minimizan. Entonces, para el segundo ejemplo anterior, las posibles divisiones son:
- Una partición: entonces el tiempo es 100.
- Dos particiones: (10) y (20, 30, 40), por lo que el tiempo es 90. Del mismo modo, podemos poner el primer divisor
después de 20 (=> tiempo 70) o 30 (=> tiempo 60); entonces esto significa que el tiempo mínimo: (100, 90, 70, 60) es 60.
Fuerza bruta: una solución de fuerza bruta es considerar todos los conjuntos posibles de particiones contiguas y calcular la partición de suma máxima en cada caso y devolver el mínimo de todos estos casos.
1) Subestructura óptima: podemos implementar la solución ingenua usando recursividad con la siguiente propiedad de subestructura óptima:
suponiendo que ya tenemos k-1 particiones en su lugar (usando k-2 divisores), ahora tenemos que colocar el k-1 th divisor para obtener k particiones.
Pregunta: ¿Cómo podemos hacer esto?
Respuesta: Podemos poner el k-1 th divisor entre el i th y el i+1 th elemento donde i = 1 a n. Tenga en cuenta que ponerlo antes del primer elemento es lo mismo que ponerlo después del último elemento.
El costo total de este arreglo se puede calcular como el máximo de lo siguiente:
- A.) El costo de la última partición: sum(Ai…..An) , donde el divisor k- 1th está
antes del elemento i . Esto se puede averiguar usando una función de ayuda simple para calcular la suma
de elementos entre dos índices en la array. - B) El costo máximo de cualquier partición ya formada a la izquierda del divisor k-1th. Podemos observar que esto es en realidad para colocar los separadores k-2 de la manera más justa posible, por lo que es un subproblema del problema dado. Por lo tanto, podemos escribir la propiedad de subestructura óptima como la siguiente relación de recurrencia:
La siguiente es la implementación de la ecuación recursiva anterior:
C++
// CPP program for The painter's partition problem
#include <climits>
#include <iostream>
using namespace std;
// function to calculate sum between two indices
// in array
int sum(int arr[], int from, int to)
{
int total = 0;
for (int i = from; i <= to; i++)
total += arr[i];
return total;
}
// for n boards and k partitions
int partition(int arr[], int n, int k)
{
// base cases
if (k == 1) // one partition
return sum(arr, 0, n - 1);
if (n == 1) // one board
return arr[0];
int best = INT_MAX;
// find minimum of all possible maximum
// k-1 partitions to the left of arr[i],
// with i elements, put k-1 th divider
// between arr[i-1] & arr[i] to get k-th
// partition
for (int i = 1; i <= n; i++)
best = min(best, max(partition(arr, i, k - 1),
sum(arr, i, n - 1)));
return best;
}
int main()
{
int arr[] = { 10, 20, 60, 50, 30, 40 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
cout << partition(arr, n, k) << endl;
return 0;
}
Java
// Java Program for The painter's partition problem
import java.util.*;
import java.io.*;
class GFG
{
// function to calculate sum between two indices
// in array
static int sum(int arr[], int from, int to)
{
int total = 0;
for (int i = from; i <= to; i++)
total += arr[i];
return total;
}
// for n boards and k partitions
static int partition(int arr[], int n, int k)
{
// base cases
if (k == 1) // one partition
return sum(arr, 0, n - 1);
if (n == 1) // one board
return arr[0];
int best = Integer.MAX_VALUE;
// find minimum of all possible maximum
// k-1 partitions to the left of arr[i],
// with i elements, put k-1 th divider
// between arr[i-1] & arr[i] to get k-th
// partition
for (int i = 1; i <= n; i++)
best = Math.min(best, Math.max(partition(arr, i, k - 1),
sum(arr, i, n - 1)));
return best;
}
// Driver code
public static void main(String args[])
{
int arr[] = { 10, 20, 60, 50, 30, 40 };
// 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
Python3
# Python program for The painter's # partition problem function to # calculate sum between two indices # in array def sum(arr, frm, to): total = 0; for i in range(frm, to + 1): total += arr[i] return total # for n boards and k partitions def partition(arr, n, k): # base cases if k == 1: # one partition return sum(arr, 0, n - 1) if n == 1: # one board return arr[0] best = 100000000 # find minimum of all possible # maximum k-1 partitions to # the left of arr[i], with i # elements, put k-1 th divider # between arr[i-1] & arr[i] to # get k-th partition for i in range(1, n + 1): best = min(best, max(partition(arr, i, k - 1), sum(arr, i, n - 1))) return best # Driver Code arr = [10, 20, 60, 50, 30, 40 ] n = len(arr) k = 3 print(partition(arr, n, k)) # This code is contributed # by sahilshelangia
C#
// C# Program for The painter's partition problem
using System;
class GFG {
// function to calculate sum
// between two indices in array
static int sum(int []arr, int from, int to)
{
int total = 0;
for (int i = from; i <= to; i++)
total += arr[i];
return total;
}
// for n boards and k partitions
static int partition(int []arr, int n, int k)
{
// base cases
if (k == 1) // one partition
return sum(arr, 0, n - 1);
if (n == 1) // one board
return arr[0];
int best = int.MaxValue;
// find minimum of all possible maximum
// k-1 partitions to the left of arr[i],
// with i elements, put k-1 th divider
// between arr[i-1] & arr[i] to get k-th
// partition
for (int i = 1; i <= n; i++)
best = Math.Min(best, Math.Max(partition(arr, i, k - 1),
sum(arr, i, n - 1)));
return best;
}
// Driver code
public static void Main()
{
int []arr = {10, 20, 60, 50, 30, 40};
// Calculate size of array.
int n = arr.Length;
int k = 3;
// Function calling
Console.WriteLine(partition(arr, n, k));
}
}
// This code is contributed by vt_m
PHP
<?php
// PHP program for The
// painter's partition problem
// function to calculate sum
// between two indices in array
function sum($arr, $from, $to)
{
$total = 0;
for ($i = $from; $i <= $to; $i++)
$total += $arr[$i];
return $total;
}
// for n boards
// and k partitions
function partition($arr, $n, $k)
{
// base cases
if ($k == 1) // one partition
return sum($arr, 0, $n - 1);
if ($n == 1) // one board
return $arr[0];
$best = PHP_INT_MAX;
// find minimum of all possible
// maximum k-1 partitions to the
// left of arr[i], with i elements,
// put k-1 th divider between
// arr[i-1] & arr[i] to get k-th
// partition
for ($i = 1; $i <= $n; $i++)
$best = min($best,
max(partition($arr, $i, $k - 1),
sum($arr, $i, $n - 1)));
return $best;
}
// Driver Code
$arr = array(10, 20, 60,
50, 30, 40);
$n = sizeof($arr);
$k = 3;
echo partition($arr, $n, $k), "\n";
// This code is contributed by ajit
?>
Javascript
<script>
// JavaScript Program for The painter's
// partition problem
// Function to calculate sum between
// two indices in array
function sum(arr, from, to)
{
let total = 0;
for(let i = from; i <= to; i++)
total += arr[i];
return total;
}
// For n boards and k partitions
function partition(arr, n, k)
{
// Base cases
if (k == 1) // one partition
return sum(arr, 0, n - 1);
if (n == 1) // one board
return arr[0];
let best = Number.MAX_VALUE;
// Find minimum of all possible maximum
// k-1 partitions to the left of arr[i],
// with i elements, put k-1 th divider
// between arr[i-1] & arr[i] to get k-th
// partition
for(let i = 1; i <= n; i++)
best = Math.min(best,
Math.max(partition(arr, i, k - 1),
sum(arr, i, n - 1)));
return best;
}
// Driver Code
let arr = [ 10, 20, 60, 50, 30, 40 ];
// Calculate size of array.
let n = arr.length;
let k = 3;
document.write(partition(arr, n, k));
// This code is contributed by susmitakundugoaldanga
</script>
Producción
90
Complejidad temporal: La complejidad temporal de la solución anterior es exponencial.
Espacio Auxiliar: O(1)
2) Subproblemas superpuestos: A continuación se muestra el árbol de recurrencia parcial para T(4, 3) en la ecuación anterior.
T(4, 3)
/ / \ ..
T(1, 2) T(2, 2) T(3, 2)
/.. /..
T(1, 1) T(1, 1)
Podemos observar que muchos subproblemas como T(1, 1) en el problema anterior se resuelven una y otra vez. Debido a estas dos propiedades de este problema, podemos resolverlo mediante programación dinámica , ya sea mediante el método memorizado de arriba hacia abajo o el método tabular de abajo hacia arriba
.
La siguiente es la implementación tabular de abajo hacia arriba:
C++
// A DP based CPP program for painter's partition problem
#include <climits>
#include <iostream>
using namespace std;
// function to calculate sum between two indices
// in array
int sum(int arr[], int from, int to)
{
int total = 0;
for (int i = from; i <= to; i++)
total += arr[i];
return total;
}
// bottom up tabular dp
int findMax(int arr[], int n, int k)
{
// initialize table
int dp[k + 1][n + 1] = { 0 };
// base cases
// k=1
for (int i = 1; i <= n; i++)
dp[1][i] = sum(arr, 0, i - 1);
// n=1
for (int i = 1; i <= k; i++)
dp[i][1] = arr[0];
// 2 to k partitions
for (int i = 2; i <= k; i++) { // 2 to n boards
for (int j = 2; j <= n; j++) {
// track minimum
int best = INT_MAX;
// i-1 th separator before position arr[p=1..j]
for (int p = 1; p <= j; p++)
best = min(best, max(dp[i - 1][p],
sum(arr, p, j - 1)));
dp[i][j] = best;
}
}
// required
return dp[k][n];
}
// driver function
int main()
{
int arr[] = { 10, 20, 60, 50, 30, 40 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
cout << findMax(arr, n, k) << endl;
return 0;
}
Java
// A DP based Java program for
// painter's partition problem
import java.util.*;
import java.io.*;
class GFG
{
// function to calculate sum between two indices
// in array
static int sum(int arr[], int from, int to)
{
int total = 0;
for (int i = from; i <= to; i++)
total += arr[i];
return total;
}
// bottom up tabular dp
static int findMax(int arr[], int n, int k)
{
// initialize table
int dp[][] = new int[k+1][n+1];
// base cases
// k=1
for (int i = 1; i <= n; i++)
dp[1][i] = sum(arr, 0, i - 1);
// n=1
for (int i = 1; i <= k; i++)
dp[i][1] = arr[0];
// 2 to k partitions
for (int i = 2; i <= k; i++) { // 2 to n boards
for (int j = 2; j <= n; j++) {
// track minimum
int best = Integer.MAX_VALUE;
// i-1 th separator before position arr[p=1..j]
for (int p = 1; p <= j; p++)
best = Math.min(best, Math.max(dp[i - 1][p],
sum(arr, p, j - 1)));
dp[i][j] = best;
}
}
// required
return dp[k][n];
}
// Driver code
public static void main(String args[])
{
int arr[] = { 10, 20, 60, 50, 30, 40 };
// Calculate size of array.
int n = arr.length;
int k = 3;
System.out.println(findMax(arr, n, k));
}
}
// This code is contributed by Sahil_Bansall
Python3
# A DP based Python3 program for # painter's partition problem # function to calculate sum between # two indices in list def sum(arr, start, to): total = 0 for i in range(start, to + 1): total += arr[i] return total # bottom up tabular dp def findMax(arr, n, k): # initialize table dp = [[0 for i in range(n + 1)] for j in range(k + 1)] # base cases # k=1 for i in range(1, n + 1): dp[1][i] = sum(arr, 0, i - 1) # n=1 for i in range(1, k + 1): dp[i][1] = arr[0] # 2 to k partitions for i in range(2, k + 1): # 2 to n boards for j in range(2, n + 1): # track minimum best = 100000000 # i-1 th separator before position arr[p=1..j] for p in range(1, j + 1): best = min(best, max(dp[i - 1][p], sum(arr, p, j - 1))) dp[i][j] = best # required return dp[k][n] # Driver Code arr = [10, 20, 60, 50, 30, 40] n = len(arr) k = 3 print(findMax(arr, n, k)) # This code is contributed by ashutosh450
C#
// A DP based C# program for
// painter's partition problem
using System;
class GFG {
// function to calculate sum between
// two indices in array
static int sum(int []arr, int from, int to)
{
int total = 0;
for (int i = from; i <= to; i++)
total += arr[i];
return total;
}
// bottom up tabular dp
static int findMax(int []arr, int n, int k)
{
// initialize table
int [,]dp = new int[k+1,n+1];
// base cases
// k=1
for (int i = 1; i <= n; i++)
dp[1,i] = sum(arr, 0, i - 1);
// n=1
for (int i = 1; i <= k; i++)
dp[i,1] = arr[0];
// 2 to k partitions
for (int i = 2; i <= k; i++) { // 2 to n boards
for (int j = 2; j <= n; j++) {
// track minimum
int best = int.MaxValue;
// i-1 th separator before position arr[p=1..j]
for (int p = 1; p <= j; p++)
best = Math.Min(best, Math.Max(dp[i - 1,p],
sum(arr, p, j - 1)));
dp[i,j] = best;
}
}
// required
return dp[k,n];
}
// Driver code
public static void Main()
{
int []arr = {10, 20, 60, 50, 30, 40};
// Calculate size of array.
int n = arr.Length;
int k = 3;
Console.WriteLine(findMax(arr, n, k));
}
}
// This code is contributed by vt_m
PHP
<?php
// A DP based PHP program for
// painter's partition problem
// function to calculate sum
// between two indices in array
function sum($arr, $from, $to)
{
$total = 0;
for ($i = $from; $i <= $to; $i++)
$total += $arr[$i];
return $total;
}
// bottom up tabular dp
function findMax($arr, $n, $k)
{
// initialize table
$dp[$k + 1][$n + 1] = array( 0 );
// base cases
// k=1
for ($i = 1; $i <= $n; $i++)
$dp[1][$i] = sum($arr, 0,
$i - 1);
// n=1
for ($i = 1; $i <= $k; $i++)
$dp[$i][1] = $arr[0];
// 2 to k partitions
for ($i = 2; $i <= $k; $i++)
{
// 2 to n boards
for ($j = 2; $j <= $n; $j++)
{
// track minimum
$best = PHP_INT_MAX;
// i-1 th separator before
// position arr[p=1..j]
for ($p = 1; $p <= $j; $p++)
$best = min($best, max($dp[$i - 1][$p],
sum($arr, $p, $j - 1)));
$dp[$i][$j] = $best;
}
}
// required
return $dp[$k][$n];
}
// Driver Code
$arr = array (10, 20, 60,
50, 30, 40 );
$n = sizeof($arr);
$k = 3;
echo findMax($arr, $n, $k) ,"\n";
// This code is contributed by m_kit
?>
Javascript
<script>
// A DP based Javascript program for
// painter's partition problem
// function to calculate sum between
// two indices in array
function sum(arr, from, to)
{
let total = 0;
for (let i = from; i <= to; i++)
total += arr[i];
return total;
}
// bottom up tabular dp
function findMax(arr, n, k)
{
// initialize table
let dp = new Array(k+1);
for(let i = 0; i < k + 1; i++)
{
dp[i] = new Array(n + 1);
}
// base cases
// k=1
for (let i = 1; i <= n; i++)
dp[1][i] = sum(arr, 0, i - 1);
// n=1
for (let i = 1; i <= k; i++)
dp[i][1] = arr[0];
// 2 to k partitions
for (let i = 2; i <= k; i++) { // 2 to n boards
for (let j = 2; j <= n; j++) {
// track minimum
let best = Number.MAX_VALUE;
// i-1 th separator before position arr[p=1..j]
for (let p = 1; p <= j; p++)
best = Math.min(best, Math.max(dp[i - 1][p],
sum(arr, p, j - 1)));
dp[i][j] = best;
}
}
// required
return dp[k][n];
}
// Driver code
let arr = [10, 20, 60, 50, 30, 40];
// Calculate size of array.
let n = arr.length;
let k = 3;
document.write(findMax(arr, n, k));
// This code is contributed by mukesh07.
</script>
Producción
90
Complejidad temporal:
Espacio auxiliar: O(k*N)
3) Optimizaciones adicionales: la complejidad de tiempo del programa anterior es 
. Se puede reducir fácilmente 
precalculando las sumas acumulativas en una array, evitando así llamadas repetidas a la función de suma:
C++
int sum[n+1] = {0};
// sum from 1 to i elements of arr
for (int i = 1; i <= n; i++)
sum[i] = sum[i-1] + arr[i-1];
for (int i = 1; i <= n; i++)
dp[1][i] = sum[i];
// and using it to calculate the result as:
best = min(best, max(dp[i-1][p], sum[j] - sum[p]));
Java
int sum[] = new int[n+1]; // sum from 1 to i elements of arr for (int i = 1; i <= n; i++) sum[i] = sum[i-1] + arr[i-1]; for (int i = 1; i <= n; i++) dp[1][i] = sum[i]; // and using it to calculate the result as: best = Math.min(best, Math.max(dp[i-1][p], sum[j] - sum[p])); // This code is contributed by divyesh072019.
Python3
sum = [0] * (n + 1) # sum from 1 to i elements of arr for i in range(1, n + 1): sum[i] = sum[i-1] + arr[i-1] for i in range(1, n + 1): dp[1][i] = sum[i] # and using it to calculate the result as: best = min(best, max(dp[i-1][p], sum[j] - sum[p])); # This code is contributed by kraanzu.
C#
int[] sum = new int[n+1]; // sum from 1 to i elements of arr for (int i = 1; i <= n; i++) sum[i] = sum[i-1] + arr[i-1]; for (int i = 1; i <= n; i++) dp[1,i] = sum[i]; // and using it to calculate the result as: best = Math.Min(best, Math.Max(dp[i-1][p], sum[j] - sum[p])); // This code is contributed by divyeshrabadiya07.
Javascript
<script> let sum = new Array(n+1); // sum from 1 to i elements of arr for (let i = 1; i <= n; i++) sum[i] = sum[i-1] + arr[i-1]; for (let i = 1; i <= n; i++) dp[1][i] = sum[i]; // and using it to calculate the result as: best = Math.min(best, Math.max(dp[i-1][p], sum[j] - sum[p])); // This code is contributed by Saurabh Jaiswal. </script>
2) Aunque aquí consideramos dividir A en k o menos particiones, podemos observar que
el caso óptimo siempre ocurre cuando dividimos A exactamente en k particiones. Entonces podemos usar:
C++
for (int i = k-1; i <= n; i++) best = min(best, max( partition(arr, i, k-1), sum(arr, i, n-1)));
Java
for (int i = k-1; i <= n; i++) best = Math.min(best, Math.max(partition(arr, i, k-1), sum(arr, i, n-1))); // This code is contributed by pratham76.
Python3
for i range(k-1,n+1): best=min(best, max(partition(arr, i, k-1),sum(arr, i, n-1))) # This code is contributed by Aman Kumar.
C#
for(int i = k - 1; i <= n; i++) best = Math.Min(best, Math.Max(partition(arr, i, k - 1), sum(arr, i, n - 1))); // This code is contributed by rutvik_56
Javascript
for(var i = k - 1; i <= n; i++) best = Math.min(best, Math.max(partition(arr, i, k - 1), sum(arr, i, n - 1))); // This code is contributed by Ankita saini
Ejercicio:
¿Puede encontrar una solución utilizando la búsqueda binaria? Consulte Asignar un número mínimo de páginas para obtener más detalles.
Referencias:
https://articles.leetcode.com/the-painters-partition-problem/
Publicación traducida automáticamente
Artículo escrito por rsatish1110 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA