1
$\begingroup$

You are given a sequence of n integers. Partition the sequence into segments such that the sum of the integers in each segment is smaller than a given cap K. Give an algorithm that minimizes the number of segments. Source of this question

Example:

Sequence = [2 4 3]
K = 7

In this case, there are 2 optimal solutions:
[2, 4], [3]
[2], [4, 3]
And one suboptimal solution:
[2], [4], [3]

Assume all integers in the sequence are smaller than K.

Here's the greedy algorithm:

sum = 0 
segments = 1  #for convenience, assume the sequence is not empty.  
For each integer i in the sequence:  
    if sum + i <= K:
        sum += i
    else
        sum = 0
        segments += 1
return segments

I have trouble proving that this algorithm is optimal in the sense that it minimizes the number of segments.

This is my attempt at a proof of optimality:

Suppose there is a function $F$ which, given a sequence of integers, returns the minimal number of segments for that sequence.

Suppose we are iterating through the sequence and we have gone past some number of elements and there are some elements remaining [$e_x, e_{x+1}, e_{x+2}, ...$]. Suppose we have the option of including $e_x$ in our current segment (i.e the sum of the segment including $e_x$ will not exceed K), whether or not we choose to include $e_x$ determines the number of elements remaining after the current segment is finished. If we do not include $e_x$ in the current segment then the number of remaining segments is at least $F([e_x, e_{x+1}, e_{x+2}, ...])$, and if we do include it then it is at least $F([e_{x+1}, e_{x+2}, ...])$.

So now I need to prove that $F([e_x, e_{x+1}, e_{x+2}, ...])$ is at least $F([e_{x+1}, e_{x+2}, ...])$ but this feels like I'm going around in circles. I have no idea how to proceed.

$\endgroup$
  • $\begingroup$ I think an exchange argument is probably sufficient. $\endgroup$ – user2108462 Aug 24 '18 at 21:45
1
$\begingroup$

I am assuming that we have a sequence of non-negative integers, because if they are not, then $$[7,-1,6,2] \quad \text{and} \quad K=7$$ has optimal solution $[7], [-1,6,2]$, but greedy algorithm would give $[7,-1],[6],[2]$.

This example might also give a clue to the proof for optimality of greedy algorithm for non-negative integers. As you said, suppose that $F$ is a function that takes a sequence and returns its optimal number of segments.

Let $[n_1,n_2\ldots,n_m]$ be a sequence of non-negative integers. Then, to show that greedy algorithm is optimal, we must show that for all sequences and for all $k$ such that $F([n_1,\ldots,n_k]) = F([n_1,\ldots,n_{k-1}])$ , $$F([n_{k+1},\ldots,n_m]) \leq F([n_k,\ldots,n_m]).$$ where LHS is greedy and RHS is alternative, because greedy will take $n_k$ if it can.

I think this is clear because all it says is that we cannot have less segments with more (non-negative!) element in the sequence. If $F([n_{k+1},\ldots,n_m]) = s$, then adding $n_k$ to the front of the sequence cannot make $F([n_k,\ldots,n_m])$ to be less than $s$. If it could, then the optimal algorithm could also produce less than $s$ segments without the "help" of $n_k$. It can in best case scenario "join" $n_k$ to existing segment or create one more segment, because non-negative $n_k$ is a "burden".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.