Combination of elements with a defined constraint (edited)

Question

I'm trying to program a solution for this problem. So let's say I have a finite set elements ${X_{1},X_{2} , ..., X_{N}}$. To each element $X_{i}$ from the set, there is some assigned value, let's say $k_{i}$ and length $l_{i}$. I want to find, for example, the top n, $1 \leqslant n \leqslant N$ , combination of elements such that the sum of the assigned values is maximized and that the length doesn't exceed some constant K.

So I can just find all combinations and calculate the sum of the values and choose the top n. But for a large set and constraint, this would be a very inefficient way. Do you guys have a more efficient way of tackling this problem?

Thanks in advance!

Answer 1

Sort $X_1,...,X_N$ based on their weights $k_i$. Then you can find combinations that fit the criteria with maximum number of elements. Any subsets of these combinations obviously also fit the bill. That should offer a considerable speedup.