Knapsack Problem with Constraints on Item Values

Question

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 $p\gets$ median of values in $A$;

   2.2 $R\gets$ items whose value is greater than $p$;

   2.3 $L\gets A\setminus R$; (items whose value is smaller than $p$)

   2.4 $W_R\gets$ $\sum_{A[i]\in R}w_i$;

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

   2.6 $A\gets R$;

3. $W\gets 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! :)

Answer 1

Yes your algorithm runs in $O(n)$ time if you use the median of medians algorithm. You can prove that to yourself by looking at your algorithm and noting that in every loop the size of the array we are considering is cut in halve. And the runtime of the loop body is $O(n)$ (if we use median of medians and array copying/filtering is $O(n)$ anyway). Now we get the following sum:

$$\sum_{i=0}^{\log(n)} \frac{n}{2^i} \leq \sum_{i=0}^{\infty} \frac{n}{2^i} = n\cdot\sum_{i=0}^{\infty} \frac{1}{2^i} = 2n \in O(n)$$

The $\log(n)$ comes from the fact that you can only divide the array size $log(n)$ times in halves until you arrive at $1$ (because $2^{\log(n)} = n$). Every term of the sum expresses the cost of one execution of the loop body.