constrained assignment optimization problem

Question

I have a large number of objects $r$, in a store, $M=\{r_1, r_2, …., r_N\}$, with size $D$. The objects have different lengths $l_i$ and selling prices $ρ_i$, $ρ_iϵ[0,1]$, such that $\forall r\in M$: $$\sum_{i=1}^{|M|} ρ_i≤1$$ From set M, I want to store the $k$ number of objects in a container $C$, of length $L$ where $|C|<|M|$. Given the constraint that: $$\sum_{k=1}^{|C|} l_k≤L$$ How can I make the best selection among the objects so that I can get an optimal price at the container? i.e., obtain: $$\max\sum_{k=1}^{|C|}ρ_k, \forall r\in C.$$ Which algorithms give me the est-combining solution with minimized computational complexity? Any suggestion is appreciable; thank you!

Answer 1

This sounds similar to the popular knapsack problem and problems of this type usually are tackled via dynamic programming. The complexity then is of order $O(LN)$, as far as I remember. Your example is slightly differnt, though, in the sense that your "knapsack" is not only limited by volume, but also by number of items. I suspect the algorithm may be modified straighforwardly.