4
$\begingroup$

Assume that $A$ is the set of objects such that each object $x_i \in A$ has value $w_i$. We wish to pack these objects into group, each pack containing at least $k$ objects. Our goal is to minimize the maximum difference between the maximum and minimum value of each packs. in other words, our goal is to minimize $L$ with the constraint that all packs should have more than $k$ object in them.

$$L = \max_{i \in \mathrm{packs}} \left\{\max_{j \in \mathrm{pack}(i)}w_j - \min_{k \in \mathrm{pack}(i)}w_k \right\}.$$

For example for the following packing, $L$ is $\max{(30-20, 120 - 100)} = 20$. $$[20, 30] \;\; [100,110,120]$$

I was wondering if there is a greedy algorithm that can do the job.

$\endgroup$
  • 2
    $\begingroup$ I don't know if greedy can do the entire job optimally, but here's a small hint: There's an important property to be exploited here that rules out a large class of solutions from optimality, enabling an $O(n^2)$ DP solution. $\endgroup$ – j_random_hacker Apr 1 at 16:15
  • $\begingroup$ I think using the fact that in the optimal answer, the last pack should contain at most $2k-1$ objects (a pack with $2k$ objects can be split in two packs with $k$ objects) we can construct the $O(n^2)$ DP solution. $\endgroup$ – user102344 Apr 2 at 7:48
1
$\begingroup$

I would not believe there is a greedy algorithm that can do the job. Instead, sorting followed by dynamic programming as indicated by j_random_hacker's comment seems the appropriate way to find $L$.


Let $n$ be the number of given objects. Assume $k\le n$; otherwise there is no such packing.

First, sort all the weights so that we will have $w_0\le w_2\le \cdots\le w_{n-1}$. Then there is an optimal packing in which each pack consists of consecutive weights. That fact enables dynamic programming, since we can consider only that kind of packing, which has a natural last pack.

Given a packing $P$, let $L(P)$ be the maximum difference between the maximum and minimum value of each pack in $P$. Let $dp[i]$ be the minimum of $L(P)$ for all packings of the weights $w_0, w_1,\cdots, w_i$, where $k-1\le i\le n-1$. The final answer for all $n$ weights is $dp[n-1]$.

The base case is $dp[i] = w_i-w_0$ for $k-1\le i\lt 2k-1$, as there can be only one pack that contains all the weights.

What if $i\ge 2k-1$? Note that a packing with its last pack removed is still a packing. That critical observation tells us that $dp[i]$ is the minimum of $$\begin{align} &\max(dp[i-k],\ w_i-w_{(i-k)+1}), \\ &\max(dp[i-k-1],\ w_i-w_{(i-k-1)+1}), \\ &\max(dp[i-k-2],\ w_i-w_{(i-k-2)+1}), \\ &\cdots,\\ &\max(dp[i-k-\ell],\ w_i-w_{(i-k-\ell)+1}), \\ &\cdots, \end{align}$$ where the list stops right before $\ell$ becomes $k$, since we can ignore the packings where the last pack (in fact, any pack) contains at least $2k$ objects. We can always split those objects into 2 valid packs, which will not increase $L(P)$. We can also stop as soon as $w_i-w_{(i-k-\ell)+1}$ is no less than the minimum so far.

The time-complexity of algorithm is $O(n\log n + nk)$.

$\endgroup$

Your Answer

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