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! :)

• dshin: This indeed looks like a linear time algorithm to me.
• plshelp: I understand that you have to repeat the algorithm for $L$ because the loop can only make the number of elements you use smaller thus potentially making it to small which makes the second search on $L$ necessary. My question is how do you know hat this wouldn't occur again for $L$? I mean that you again choose too few items and would need another search?
• ArGenya: @plshelp Please notice that the construction and update for $L$ in step 2. In the last iteration of the loop (before $W_{\mathrm{total}}$ is updated) we have that $W_{\mathrm{total}} = \sum_{A[i]\in L} w_i + \sum_{A[j]\in R}w_j > W,ドル while the sum of weights in $R$ does not exceed $W$. Thus it suffices to pick the elements in $L$.
• plshelp: @ArGenya I understand your point; it is only necessary to search through $L$ after the first pass. I just wonder that if you apply step 2. to $L$ in the last iteration before ($W_{\text{total}}$ is updated) it'll have the value $W_{\text{total}} = \Sigma_{A[i]\in Q} \omega_i + \Sigma_{A[j] \in L'} \omega_j$. Where $L'$ is basically the new $R$ and $Q$ the new $L$ (for the execution of 2. for $L$). Now you would have to execute 2. for $Q$ again for sufficiently large samples? Or am I missing something? Why is $Q$ empty?
• plshelp: More executions won't make the runtime worse since you still always cut in halve.

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.