Optimal integer partitions

Let n be a positive integer and let g 1 , … , g n be real numbers. The following integer partition problem (IPP) is studied: find a partition of the integer n = ∑ i = 1 n i ⋅ λ i such that ∑ i = 1 n g i ⋅ λ i is maximal. An extended variant of the IPP is the problem EIPP, where, as a secondary condition, the number ∑ i = 1 n λ 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 } . It is proved that there is always an optimal solution for the IPP (as well as for the EIPP) whose support contains at most ⌊ log 2 ( n + 1 ) ⌋ elements and that this bound is sharp. An algorithm of time complexity O ( n 2 ) for the determination of such an optimal solution is presented. Finally the following non-polynomial bounds for the maximum number M ( n ) of all optimal solutions for the EIPP are proved: 2.2324 n 1 / 3 ≲ ln M ( n ) ≲ 1 3 6 3 n 1 / 3 ln n  as  n → ∞ .