Jaki rodzaj algorytmu? (Plecaka, Bin Packing !?)

Question

Problem jest następujący:

pan n potknąć długości w km, który powinien być podzielony między liczbą m dni takie, że maksymalna suma długości dziennie jest zminimalizowane. Na przykład. Długości Trip [1,5,2,6,8,3,2] podzielone między 3 dni powodują [1,5,2] [6] [8,3,2], ponieważ maksymalne sumy długości dnia wynoszą najniższe możemy osiągnąć.

Czy istnieje jakiś algorytm opisujący sposób postępowania z takim problemem? Natknąłem się na opakowanie do pakowania i problem z plecakiem, ale żaden z nich nie dotyczy mojego problemu. Mogę sobie wyobrazić, że może to być mała modyfikacja pakunku bin, ale nie dochodzę do wniosku.

Answer 1

Ten problem można rozwiązać za pomocą Binary Search

Załóżmy, że maksymalna długość wynosi X, możemy łatwo sprawdzić, czy możemy podzielić wyjazdy na dni mz maksymalną długość każdego dnia nie jest większa niż X przez to następujące chciwy:

boolean isValid(int X){ 
    int currentLength = 0; 
    int numberOfDays = 1; 
    for(int i = 0; i < n; i++) 
     if (trip[i] > X) 
     return false; 
     if(currentLength + trip[i] <= X){ 
     currentLength += trip[i]; 
     }else{ 
     currentLength = trip[i]; 
     numberOfDays++; 
     } 
    } 
    return numberOfDays <= m; 
} 

Następnie, możemy łatwo znaleźć minimum dla X następującym wyszukiwaniu binarnym:

int start = 0; 
int end = sum of all trips; 
int result = end; 
while(start <=end){ 
    int mid = (start + end)/2; 
    if(isValid(mid)){ 
     result = mid; 
     end = mid - 1; 
    }else{ 
     start = mid + 1; 
    } 
} 

Złożoność czasu to O (n log z) z z to suma wszystkich podróży.

Answer 2

Może być rozwiązany za pomocą podejścia do programowania dynamicznego, gdzie stan jest zdefiniowany jako DP[i][j], gdzie i odnosi się do końcowego indeksu dnia, a j utrzymuje dotychczasowe liczby dni. Możesz przejść do następnego stanu i wziąć maksymalną sumę dnia odpowiadającą bieżącemu ruchowi, a następnie porównać go do całkowitego minimum.

Napisałem rekursywne dynamiczne rozwiązanie programistyczne w języku C++, może być trochę trudno zrozumieć, jak działają przejścia stanów, aby móc je zrozumieć, może zajść potrzeba zajrzenia do programowania dynamicznego z pamięcią.

#include <iostream> 
#define INF 1000000000 
using namespace std; 

int n, m, dist[100] = {1,5,2,6,8,3,2}, dp[1000][1000]; 

int solve(int index, int count){ 
    if(index == n){ 
     if(count == m) return 0; 
     else return INF; 
    } 
    if(dp[index][count] != -1) return dp[index][count]; 
    int sum = 0, ans = INF; 
    for(int i = index;i < n;i++){ 
     sum += dist[i]; 
     int val = max(sum, solve(i+1, count+1)); 
     ans = min(ans, val); 
    } 
    return dp[index][count] = ans; 
} 

int main() { 
    // your code goes here 
    n = 7, m = 3; 
    for(int i = 0;i < 1000;i++) for(int j = 0;j < 1000;j++) dp[i][j] = -1; 
    cout << solve(0, 0) << endl; 
    return 0; 
} 

Link do rozwiązania Ideone: https://ideone.com/glHsgF

Answer 3

To ani plecaka ani Bin pakowania. Powszechnie nazywa się problem z partycją k.
Jak wspomniano w komentarzach, można to zrobić za pomocą programowania dynamicznego.

DP[N,M] - minimum cost of partitioning the array = {a1, ... , aN} into M partitions. 
      Where cost is defined as the maximum sum of each partition. 
DP[1,m] = a1 
DP[n,1] = Sum of all elements in the array {a1, ... , an} 
DP[n,m] = min over k from 1 to n (max(DP[n-k,m-1],sum of elements n-k to n))