Quel type d'algorithme? (Knapsack, Bin Packing !?)

Question

Le problème est le suivant:

Vous avez déclenchement n longueurs en km qui doivent être réparties entre le nombre de jours de m tel que la somme maximale de longueurs par jour est réduit au minimum. Par exemple. Les longueurs de voyage [1,5,2,6,8,3,2] répartis entre 3 jours dans le résultat [1,5,2] [6] [8,3,2] parce que le maximum des sommes de longueur du jour est le plus bas possible.

Existe-t-il un type d'algorithme qui décrit la gestion d'un tel problème? Je suis tombé sur Ben emballage et le problème de sac à dos, mais aucun d'entre eux couvre mon problème. J'imagine que ce pourrait être une petite modification de l'emballage de la poubelle, mais n'arrive pas à une conclusion.

Answer 1

Ce problème peut être résolu en utilisant la recherche binaire

On suppose que la longueur maximale est X, nous pouvons facilement vérifier si nous pouvons diviser les voyages en jours m avec une longueur maximale pour chaque jour ne dépasse pas X par ce qui suit gourmand:

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; 
} 

Ensuite, on peut facilement trouver le minimum pour X par la recherche binaire suivante:

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; 
    } 
} 

La complexité temporelle est O (n log z) avec z est la somme de tous les déplacements.

Answer 2

Il peut être résolu en utilisant une approche de programmation dynamique où l'état est défini comme DP[i][j] où i se réfère à l'indice de fin d'un jour et j conserve le nombre de jours jusqu'à présent. Vous pouvez passer à l'état suivant et prendre la somme maximale d'un jour correspondant au mouvement en cours, puis le comparer au minimum global.

J'ai écrit une solution de programmation dynamique récursive en C++, il peut être difficile de comprendre comment les transitions d'état fonctionnent, vous devrez peut-être regarder dans la programmation dynamique avec memoisation pour le comprendre.

#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; 
} 

Lien vers la solution Ideone: https://ideone.com/glHsgF

Answer 3

Il est ni, ni Knapsack Bin emballage. Son nom commun est le problème de k-partition.
Comme indiqué dans les commentaires, cela peut être fait en utilisant la programmation dynamique.

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))