  Knapsack problem (KP) is a representative combinatorial optimization problem
that aims to maximize the total profit by selecting a subset of items under
given constraints on the total weights. In this study, we analyze a generalized
version of KP, which is termed the generalized multidimensional knapsack
problem (GMDKP). As opposed to the basic KP, GMDKP allows multiple choices per
item type under multiple weight constraints. Although several efficient
algorithms are known and the properties of their solutions have been examined
to a significant extent for basic KPs, there is a paucity of known algorithms
and studies on the solution properties of GMDKP. To gain insight into the
problem, we assess the typical achievable limit of the total profit for a
random ensemble of GMDKP using the replica method. Our findings are summarized
as follows: (1) When the profits of item types are normally distributed, the
total profit grows in the leading order with respect to the number of item
types as the maximum number of choices per item type $x^{\rm max}$ increases
while it depends on $x^{\rm max}$ only in a sub-leading order if the profits
are constant among the item types. (2) A greedy-type heuristic can find a
nearly optimal solution whose total profit is lower than the optimal value only
by a sub-leading order with a low computational cost. (3) The sub-leading
difference from the optimal total profit can be improved by a heuristic
algorithm based on the cavity method. Extensive numerical experiments support
these findings.
