Knapsack Problem with Constraints on Item Values

Given $n$ items with weights $w_1,…,w_n$ and values $v_1,…,v_n$, and a weight limit $W$, the purpose is still maximizing the total value of items to be carried (while not exceeding the weight limit). Now, a new constraint is, once an item with value $v_i$ is taken, all items whose value is greater than $v_i$ must also be taken. (It is okay to assume that all $v_i$‘s are different)

My purpose is to achieve this in $O(n)$ time, and here is my attempt (suppose the input is an array $A$ of tuples $(w_i, v_i)$):

1. Calculate total weight of the items: $W_{mathrm{total}}gets sum_{i=1}^n w_i$;

2. while $(W_{mathrm{total}} > W)$ do:

   2.1 $pgets$ median of values in $A$;

   2.2 $Rgets$ items whose value is greater than $p$;

   2.3 $Lgets Asetminus R$; (items whose value is smaller than $p$)

   2.4 $W_Rgets$ $sum_{A[i]in R}w_i$;

   2.5 $W_{mathrm{total}}gets W_R$;

   2.6 $Agets R$;

3. $Wgets W- W_{mathrm{total}}$; (the remaining capacity)

4. Repeat step 2 for the array $L$, generating the array $L’$;

5. Return $L’cup A$;

Notice that the algorithm for finding the median costs linear time.

I presume that my algorithm costs $O(n)$ time since, for every iteration in each while loop, the input size halves–but I am not 100% confident of that. So does this algorithm really cost linear time? If not, what amendments can be made, or is there a general idea for designing such an algorithm that costs linear time? Any help will be much appreciated! 🙂