An algorithm for effecient resource redistribution

For those who think visually, say I've got 5 warehouses with a current stock level of # of fish, and a target level for each. How do I achieve the new target levels in as few truck shipments as possible?

Or given an array A{250, 150, 45, 205, 350}, how can it be transformed to {200, 200, 150, 320, 130} in as few transfers as possible? Moving 50 from A[0] to A[1] would be an efficient first move.

I'm sure I could muddle through this and come up with something, but I'm also sure this problem has already been solved by people smarter than me. And it's important to me that it be correct and as efficient as possible. This is a little outside my normal work, and I'm not sure how to search for something like this (I couldn't find anything).

Thanks much!

Update:
An initial thought ... find the warehouse with the biggest deficit, then find the one with the biggest (or closest matching?) surplus, do the shipment, then repeat. Seems like that would work, but I'm not sure if there's a more elegant or efficient solution. I'll add an answer once I've got the code working.

There is no polynomial-time algorithm unless $\mathsf{P}=\mathsf{NP}$. Here is a proof.

Let $d_1, d_2, \cdots, d_n$ be the change for each warehouse to reach its target level. For the example in the question, they are $200-250=-50$, $\ 200-150=50$, $\ 150-45-150=105$, $\ 320-205=115$, $\ 350-130=-220$. We assume that sum of all $d_i$'s is 0; otherwise, it is not possible.

Proposition: The target levels can be reached in less than $n-1$ steps if and only if there exist some $d_i$'s but not all of them whose sum is $0$.

Proof.

-
"$\Leftarrow$". Suppose, WLOG, $d_1+d_2+\cdots+d_k=0$ for some $1\le k\lt n$. Suppose $k\ge2$. Then we can find $d_i\le0\le d_j$ for some $1\le i,j\le k$. We can transfer $\min(-d_i, d_j)$ fish from warehouse $i$ to warehouse $j$. Then either warehouse $i$ or warehouse $j$ reaches its target level. Now we can apply math induction.

-
"$\Rightarrow$". Suppose the target levels can be reached in some $k$ steps, $k\lt n-1$. At most $k+1$ warehouses are involved in those $k$ steps. The sum of changes for those warehouses must be 0. Note that $k+1

Let us consider the following warehouse-distribution problem, which is an easier version of the original warehouse-distribution problem.

Given $n$ warehouses with some fish and their target levels of fish,
can we use less than $n-1$ transfers to reach their target levels?

Let us recall, as explained in the Wikipedia article subset sum problem, it is $\mathsf{NP}$-hard to decide, given a multiset of integers, whether there is a non-empty subset whose sum is zero.
Given a multiset of integers $f_1, f_2, \cdots, f_n$, we can construct the following instance of warehouse-distribution problem. Let $f=\sum_{i=1}^n|f_i|$. Let $n+1$ warehouses have $g_1, g_2, \cdots, g_{n+1}$ fish respectively, where $g_1=f+f_1$, $g_2=f+f_2$, $\cdots$, $g_n=f+f_n$ and $g_{n+1}=nf-\sum_{i=1}^nf_i$. The target for each warehouse is $f$ fish. We can verify easily, thanks to the proposition above, that we can use less than $n$ transfers to reach all target levels if and only if there is a non-empty sub-multiset of all $f_i$'s whose sum is zero. Hence, the warehouse-distribution problem is at least as hard as the subset sum problem.

Since a polynomial-time algorithm is unlikely, let me give an algorithm of time-complexity about $O(n2^n)$.

-
Compute the changes, $d_1, d_2, \cdots, d_n$.

-
For each subset $S$ of $\{1,2,\cdots, n\}$, compute $\sigma(S)=\Sigma_{i\in S}d_i$. When $\sigma(S)=0$ and $S$ is non-empty, $S$ will be called a zero-set.

-
For each subset $S$, let $p(S)$ be the biggest number of disjoint subsets of $S$ that are zero-sets. $p(\emptyset)=0$. For non-empty $S$, use the following recurrence relation to compute $p(S)$. A proof of the recurrence relation is given later.
$$p(S) = \begin{cases}
\max_{a\in S} p(S\setminus\{a\}) & \text{if }S\text{ is not a
zero-set} \\
1 + \max_{a\in S} p(S\setminus\{a\}) & \text{if }S\text{ is a
zero-set} \\
\end{cases}$$
where $S\setminus\{a\}$ means $S$ without $a$.

-
The answer is $n-p(\{1,2,\cdots,n\})$.

First, for any subset $S$, we have
$$\max_{a\in S} p(S\setminus\{a\})\le p(S)\le 1 + \max_{a\in S} p(S\setminus\{a\}).$$

Suppose $S'$ is a subset of $S$. Since any disjoint subsets of $S'$ can be considered as disjoint subsets of $S$, we have $p(S')\le p(S)$. In particular, for any number $a\in S$, we have $p(S\setminus\{a\})\le P(S)$.

Suppose $S_1, S_2, \cdots, S_{p(S)}$ be some disjoint subsets of $S$ that are zero-sets. Let $a\in S_1$. Then $S_2, S_3, \cdots, S_{p(S)}$ are also disjoint subsets of $S\setminus\{a\}$, i.e., $P(S)=1+(P(S)-1)\le 1+ p(S\setminus\{a\})$. $\quad\checkmark$.

Now, Let me explain the recurrence relation in the step 3 above.

There are two cases.

-
$S$ is not a zero-set.

Suppose $S_1, S_2, \cdots, S_{P(S)}$ are disjoint subsets of $S$ that are zero-sets. If the union of all these subsets is $S$, then $S$ must a zero-set as well, which is not true. So there is a number $a\in S$ that is not in any of $S_1, S_2, \cdots, S_{P(S)}$. That means all of $S_1, S_2, \cdots, S_{P(S)}$ are subsets of $S\setminus\{a\}$. That is, $P(S) \le P(S\setminus\{a\})$. So, $p(S) = \max_{a\in S} p(S\setminus\{a\}).$

-
$S$ is a zero-set.

Let $a\in S$. Suppose we have disjoint subsets $S_1, S_2, \cdots, S_d$ of $S\setminus\{a\}$ that are zero-sets. Let $S_{d+1}$ be all the numbers in $S$ but not in any of those subsets. $S_{d+1}$ contains $a$. $S_{d+1}$ is also a zero-set since $\sigma(S_{d+1})=\sigma(S)-\sigma(S_1)-\sigma(S_2)-\cdots-\sigma(S_d)=0$. Since $S_1, S_2, \cdots, S_{d+1}$ are disjoint subsets of $S$ that are zero-sets, $p(S) \ge 1 + d$. That means, $p(S)\ge 1 + \max_{a\in S} p(S\setminus\{a\}).$ So, $p(S) = 1 + \max_{a\in S} p(S\setminus\{a\}).$ $\quad\checkmark$.

StackExchange Computer Science Q#130704, answer score: 2