Below is a problem I am trying to solve:
There are $n$ people to be allocated on $k$ gondolas. The first $q_1$ persons will go with the first gondola. The first $q_2$ persons from the remaining crowd will go with the second gondola and so on. In then end: $\sum_{i=1}^{k}q_i = n, q_i\geq1$. Now if two different guys $i$ and $j$ use the same gondola, the unfamiliarity of the given gondola is increased by $u_{i,j} \geq 0$. We have to arrange the allocation of people on gondolas such that the sum of unfamiliarities of all gondolas is as small as possiblle.
There is a link to the original problem.
We try to find a solution using a following idea:
For a given $1 \leq i \leq k$ and $1 \leq j \leq n$, let $dp[i][j]$ be a solution of the problem if we only consider the first $j$ persons and $i$ gondolas. Then we have the following reccurence formula: $$dp[i][j] = max_{k<j}( dp[i-1][k] + \sum_{a = k+1}^{j}\sum_{b = a+1}^{j}u_{a,b} ) $$
Finally we come to my question:
If we denote $A[i][j]$ to be the minimal k such that the above identity holds, then $A[i][j] \leq A[i][j+1]$
Can you help me to prove that assertion?
I imagine looking up graph-partitioning algorithms would be helpful. To elaborate -
Define a fully-connected graph $G$ with vertices being people ($n$ in total) and edge-weights being their unfamiliarity i.e., nodes $i$ and $j$ are connected by an edge with weight $u_{i,j}$. In the standard graph-partitioning problem, we'd want to assign the nodes to $k$ partitions such that the sum of weights of edges across partitions is minimized. Here, instead you'd want to maximize this (in turn minimize the sum of edge-weights inside the partitions).