# Nonlinear Knapsack with small integer weights

I have a problem that looks like a 0-1 Knapsack problem, except that the value of each item is a vector of length about 5, $$v=(v_1,\dots,v_5)$$. I want to maximize the product of components of the sum of the value vectors that are selected. In other words, if $$S$$ is the set of value vectors for the selected items, I want to maximize $$\prod_{i=1}^5 \sum_{v \in S} v_i.$$

I know that there is a dynamic programming algorithm for that would be very fast for a normal Knapsack with my parameters (max weight 100, about 100 different items) but it isn't directly applicable to my problem, as in my case an optimal weight $$w$$ solution doesn't help find a weight $$w+1$$ solution.

Does a fast general algorithm for my problem exist? If not, could I preprocess the vectors in some slow way to make this fast? They are often nonzero in only one component.

• What time are you aiming for? If by max weight you mean the maximum possible value obtainable for each of the coordinates, then DP algorithm can be naturally extended for your problem with running time $100^6$ operations $\approx 0.5-5$ hours (for each of $100^5$ possible vectors, you need to determine whether you can get this vector using first $i$ items). It'll probably be much faster if implemented in a top-down fashion (since many vectors are probably unachievable). Nov 2 '21 at 18:58
• I'm looking to solve this on millions of different subsets of about 300 or so items. Actually, that could be a key to solving it efficiently! There will be a lot of overlap between the partial solutions. Nov 3 '21 at 0:37
• I'm going to try to do a divide and conquer version of the DP approach directly on the original problem rather than on this version, though. Nov 3 '21 at 0:41
• Are the components of the value vectors usually small integers, or might they be large numbers?
– D.W.
Nov 3 '21 at 17:51
• Does every item have weight 1, or do the weights vary? Are the weights positive integers?
– D.W.
Nov 3 '21 at 22:58

Let $$S_j$$ denote the set of value vectors that are nonzero only in the $$j$$th coordinate. Sort them by decreasing value. Let $$t_{j,w}$$ denote the sum of the $$j$$th coordinates of the $$w$$ largest vectors in $$S_j$$. Then your problem becomes to find $$w=(w_1,\dots,w_5)$$ such that
$$t_{1,w_1} \times \cdots \times t_{5,w_5}$$
is maximized, subject to $$w_1+\dots+w_5 \le 100$$. This can be solved using dynamic programming, with fewer than $$5 \times 100^2$$ steps of computation. In particular, for each $$j,w$$, we compute the maximum possible value of $$t_{1,w_1} \times \dots \times t_{j,w_j}$$ subject to $$w_1+\dots+w_j \le w$$. This can be done efficiently using dynamic programming, by solving the subproblems in order of increasing $$j$$. The solution for $$j=5$$ and $$w=100$$ then gives a solution to your original problem.
What if a few of the items have more than one non-zero coordinate? One approach would be to enumerate over all possible subsets of those vectors, then for each, identify which of the remaining vectors to pick using the above algorithm. If you have 10 items with more than one non-zero coordinate, this might require something like $$2^{10} \times 5 \times 100^2$$ steps of computation (probably fewer in practice). Perhaps someone else will find a better way to handle this case.