3
$\begingroup$

The following problem statement is given: Let $S = \{s_1, s_2, \cdots, s_n\}$ be a sequence of unique positive integers and $K$ a positive integer, where $K \ge s_i$ for every $i$ between $1$ and $n$. The goal is to find a subset of $S$ whose sum is maximum, subject to the constraint that the sum must be $\le K$. Write an approximation algorithm which computes a sum which is at least half of the optimal solution on any given input. This algorithm must run in $O(n)$ time-complexity and $O(1)$ space-complexity.

I've been searching for some simple algorithm to satisfy these conditions and the closest I've come to is this, but since it makes use of sorting, the time-complexity is brought to $O(n\log n)$.

This is taken from a set of exercises given by my uni professor as preparation for the final exam. To be honest, I am not sure whether it is his original work or not, so I don't have any relevant reference to provide.

$\endgroup$
4
  • $\begingroup$ Please credit the source where you encountered this problem statement: cs.stackexchange.com/help/referencing $\endgroup$
    – D.W.
    Commented May 12, 2023 at 18:58
  • $\begingroup$ The problem statement is not clear, as it doesn't define what is meant by the optimal solution. Please make sure the body of the post is self-contained and contains enough information to answer the question. I encourage you to edit the question to address this feedback. $\endgroup$
    – D.W.
    Commented May 12, 2023 at 19:00
  • $\begingroup$ I've made an edit to try to clarify what might be the question. Please check whether that represents your problem statement (and if not, edit it appropriately), and edit your question to credit the source where you saw this. $\endgroup$
    – D.W.
    Commented May 12, 2023 at 19:03
  • $\begingroup$ Thank you all for your answers and sorry for the untimely response. @D.W. your edit is correct and I modified my question to try and specify the source. My prof. is pretty old school and I wouldn't mention his name here, nor would I even attempt to ask him for permission. $\endgroup$
    – asparagus
    Commented May 16, 2023 at 12:11

1 Answer 1

3
$\begingroup$

The idea is to set $K/2$ as the target.

  • If there is any given number that is at least $K/2$, just return it.
  • Otherwise, all given numbers are $<K/2$.
    • If the sum of all given numbers is $\le K$, return the sum, which is the optimal solution.
    • Otherwise the sum of all given numbers is $>K$.
      Let $prefix\_sum$ be $0$ initially. We will try adding all given numbers one by one to $prefix\_sum$ until it is $\ge K/2$, at which moment it cannot be $>K$ -- otherwise the last number added must be $>K/2$. Return it.

Here is an algorithm that implements the idea concisely. It runs in $O(n)$ time and $O(1)$ space.

  1. Let $prefix\_sum = 0$.
  2. For $i$ from $1$ to $n$:
    1. If $s_i\ge K/2$, return $s_i$. Else add $s_i$ to $prefix\_sum$.
    2. If $prefix\_sum\ge K/2$, return $prefix\_sum$.
  3. Return $prefix\_sum$.
$\endgroup$
2
  • $\begingroup$ Thank you very much. All I was thinking about was different ways in which to search for the right combination of elements. It never occurred to me that just changing the target would do it. $\endgroup$
    – asparagus
    Commented May 23, 2023 at 14:20
  • $\begingroup$ You are welcome. $\endgroup$
    – John L.
    Commented May 23, 2023 at 14:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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