Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
I have a problem and need to find proper algorithm to tackle it. Basically, I have a finite set of items I, each having N distinct and discrete properties like color, shape, material i.e. I = [P1, P2, P2, ... PN]
I need to pick "best" 10 items to create a set S = [I1, I2, ... I10] with maximized "score". Points are awarded based on numerous business rules e.g. too many colors in set - bad, various sizes - good etc.
How would you approach this problem?
Your problem is just a special case which brings linear search to $O(NM)$
There is no problem to find biggest value in $M$ integers. Comparator $\lt$ will perform in $O(1)$ and total complexity will be $O(M)$.
At first, your comparator $\lt$ now takes $O(N)$ time, to check all properties.
Secondly, you need to find 10 best values, not 1. Imagine that you need just 2. Add one more variable and update it's value too while traversing your $M$ items. But it's not a good idea to check 10 variables manually. So, just create an array with 10 items and keep it sorted. While checking some item - just try to insert it in your array. Insertion means shifting smaller values (losing 10'th). This operation has constant complexity.
So, we still have $M$ items, but our comparator do ~$N$ operations, sometimes it's calling O(1) insertion operation. Total complexity is $O(NM)$.
