Algorithm to maximize shipment value in linear time, confused about wording Question: A shipment company has the option of sending containers of dollar
value $v_1, v_2, … , v_n$. They have a single container ship that can carry only
$N < n$ containers. Present a linear time algorithm to choose the containers
that maximize the shipment value.
 I don't think I am understanding the question right because cant I simply use a linear time sorting algorithm like bucket sort and then take the first $N$ values?
 A: Basically you need to find the $N-th$ greatest elements in an array: so look for them sequentially using a simple selection alghorithm. However it's not linear in $n$, it's $O(N\cdot n)$, so if $N$ is less enough you are done, but if $N \to n$, then it's $O(n^2)$ ... here is the python version:
def get_containers(values, containers):
#side case: allowed 0 at most 0 containers
if containers == 0:
    return []

#side case: allowed only 1 container -> look for maximum
if containers == 1:
    return max(values)

#side case: allowed n containers -> keep them all!
if containers == len(values):
    return values

good_containers = []
values_copy = copy.copy(values)
for container in range(1, containers):
    maximum = max(values_copy)
    good_containers.append(maximum)
    values_copy.remove(maximum)

return good_containers

A: I suspect that you're probably not allowed to use non-comparison based sorts like Bucket Sort, because the range of values may be arbitrarily large (not bounded).
The standard approach here is to use a linear selection algorithm to find the $N$th largest item. Then you can find the top $N$ items in a second pass (note that these $N$ items need not be sorted, which is how we improve on standard sorting's $O(n \log n)$ to $O(n)$).
A: $$v_1+v_2+v_3/N. v_1^2+v_2^2+v_3^3=yn$$
$$(v_1+v_2+v_3)^{1/2}=Nyn$$.
$$N<yn<n; v_3^2<n$$.
$$N<n$$.
