What kind of algorithm? (Knapsack, Bin Packing!?)

Question

The Problem is the following:

You have n trip lengths in km which should be divided among m number of days such that the maximum sum of lengths per day is minimized. E.g. The Trip lengths [1,5,2,6,8,3,2] divided among 3 days result in [1,5,2] [6] [8,3,2] because the maximum of the day length sums is the lowest we can achieve.

Is there a kind of algorithm that describes the handling of such a problem? I came across bin packing and the knapsack problem, but none of them covers my issue. I can imagine it might be a little modification of the bin packing but don't come to a conclusion.

Preconcert

It Dynamic programming problem and can be solved in O(n * m) – Foskett

Is this a college assignment or a question asked on any other questionnaire? – Freeloader

Well, the problem isn't well defined... For example a better solution then the one proposed is : [1,5,2,6,8,3,2], [], [] where the minimum day length is 0 which is better than 6. In any case, in a naive solution you could just use binpacking and use binary search on the volume parameter. – Kwon

@Kwon I think he wants the maximum among the m values to be minimized. – Foskett

Sorry, I forgot a word. I need the maximum sum of lengths per day minimized. – Preconcert

Answer 1

This problem can be solved using Binary Search

Assume that the maximum length is X , we can easily check if we can divide the trips into m days with maximum length for each day is not greater than X by this following greedy:

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

Then, we can easily find the minimum for X by the following binary search:

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

Time complexity is O(n log z) with z is the sum of all trips.

Marnimarnia

Wow that's an really nice solution !! – Foskett

Very nice, can you give a short explanation for why this greedy works? – Bevis

Answer 2

It can be solved using a Dynamic Programming approach where the state is defined as DP[i][j] where i refers to the ending index of a day and j keeps the count of the days so far. You can move to the next state and take the maximum sum of a day corresponding to the current move and then can compare it to the overall minimum.

I have written a recursive Dynamic programming solution in c++, it might be a little tough to understand as to how the state transitions are working you might need to look into Dynamic programming with memoisation to understand it.

#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 to solution Ideone : https://ideone.com/glHsgF

Foskett

Answer 3

It's neither Knapsack nor Bin Packing. It's common name is k-partition problem.
As mentioned in the comments, this can be done by using dynamic programming.

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

Bevis