# Knapsack-like problem with profit formula

Given two sets of $$N$$ integers, weights and reps, that store info about some dumbbells, find out the maximum profit by taking at most $$M$$ dumbbells. Each dumbbell can be taken at most once.

The profit is given by the following formula: $$\min(\mathit{takenweights}) \times \sum_{i=1}^m \mathit{takenreps}(i),$$ where $$m \leq M$$.

For example, if $$M = 3$$, the weights are $$3,5,6,2,4,9$$, and the reps are $$8,3,4,10,7,4$$, then the output should be $$60$$, obtained by taking the third, fifth and sixth dumbbells (minimum weight $$\min(6,4,9) = 4$$ and total rep $$4+7+4=15$$).

I was thinking of using two double arrays, one for the minimum and one for the profit, where $$dp(i,j)$$ is the maximum profit obtained by taking $$i$$ dumbbells among the first $$j$$, and $$dp_{\min}(i,j)$$ is the minimum for $$dp(i,j)$$.

However, I couldn't find a recursion formula.

Do you have any suggestions?

One simple algorithm is as follows. Start by choosing the dumbbell which is going to have the minimum weight (we are going to try all possibilities). Then take the $$M$$ dumbbells with maximal rep among those with weight above the minimum weight (if there are enough).
To implement this algorithm efficiently, start by sorting the dumbbells according to weight and according to rep (separately), and find the $$M$$ dumbbells with maximal rep. Now go over the dumbbells in order of weight, each time removing the dumbbell with lowest weight and updating the set of $$M$$ best dumbbells. If you're careful you might be able to implement this in $$O(N)$$, so together with the initial sorting, the algorithm might run in time $$O(N\log N)$$.
• Roughly speaking, each time you remove the dumbbell with the lowest weight, you check whether it is one of the $M$ best. If so, you replace it with the next best one among those which are feasible. While the latter search need not be $O(1)$ worst-case, it should be $O(1)$ amortized since you're passing through each dumbbell only once. – Yuval Filmus Apr 3 '20 at 17:21