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

  • $\begingroup$ This indeed looks like a linear time algorithm to me. $\endgroup$ – dshin Sep 20 '20 at 14:26
  • $\begingroup$ 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? $\endgroup$ – plshelp Sep 21 '20 at 9:31
  • $\begingroup$ @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$. $\endgroup$ – ArGenya Sep 21 '20 at 9:49
  • $\begingroup$ @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? $\endgroup$ – plshelp Sep 21 '20 at 10:08
  • $\begingroup$ More executions won't make the runtime worse since you still always cut in halve. $\endgroup$ – plshelp Sep 21 '20 at 10:11

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.