Optimal integer partitions

Let nn be a positive integer and let g1,…,gng1,…,gn be real numbers. The following integer partition problem (IPP) is studied: find a partition of the integer n=∑i=1ni⋅λi such that ∑i=1ngi⋅λi is maximal. An extended variant of the IPP is the problem EIPP, where, as a secondary condition, the number ∑i=1nλi of items has to be minimal. The support of the partition is the index-set of all nonzero items, i.e., {i:λi>0}{i:λi>0}. It is proved that there is always an optimal solution for the IPP (as well as for the EIPP) whose support contains at most ⌊log2(n+1)⌋⌊log2(n+1)⌋ elements and that this bound is sharp. An algorithm of time complexity O(n2)O(n2) for the determination of such an optimal solution is presented. Finally the following non-polynomial bounds for the maximum number M(n)M(n) of all optimal solutions for the EIPP are proved: 2.2324n1/3≲lnM(n)≲1363n1/3lnn  as  n→∞.