I have looked through some resources with varying success. Perhaps someone can provide a place to start. Suppose we have a finite set of real numbers, $A$, and a partition,
$A=\displaystyle\bigcup_{i=1}^n A_i$
such that $\forall i\in\{1,...,n\}: |A_i|\ge k$ where $k\in\mathbb{N}$. Suppose there is a cost function, $c:A\rightarrow \mathbb{R}^+$, such that,
$c(S)=\displaystyle\sum_{s\in S}s$
for some set $S\subset \mathbb{R}$. Our task is to construct a subset, $B\subset A$, such that the following conditions hold:
$B$ contains exactly $k$ elements from each partition set, $A_i:i=\{1,...,n\}$.
$c(B)\le c*$ where $c*\in\mathbb{R}^+$.
$c(B)$ is maximal.
Preliminary thoughts: my first thought was to consider vectors of zeros and ones corresponding to elements of $2^A$. Then restrict this set to those satisfying the partition condition. Clearly from here we can use brute force but the numbers are massive for small sets. There must be a better way - I am ignorant to much of computational and optimization theory.
Thank you for your help.
Let $x_1, x_2, \ldots, x_m$ be an instance of the NP-complete PARTITION problem. We will construct an instance of the optimization problem proposed here (converted to a decision problem) that encodes PARTITION.
Let $A = \{a_1, a_2, \dots, a_{2m}\}$. We take $n=1$ so that there is only a single partition of $A$ consisting of $A$ itself. Let $c(a_i) = x_i$ for $i=1,2,\ldots,m$ and $c(a_i) = 0$ for $i=m+1, m+2, \ldots, 2m$. Finally, take $c* = 1/2\sum_{i=1}^m x_i$ and $k = m$. We leave to the reader to observe that a solution $B$ to this problem that achieves $c(B) = \lfloor c* \rfloor$ exists iff the original PARTITION problem has a solution.
While this demonstrates that a polynomial-time algorithm to obtain an exact solution to this problem in general will be unlikely, this does not rule out the possibility of heuristic approaches for approximate solutions or even exact solutions for the specific instances that you may have in mind.