2
$\begingroup$

You are given a list of prices (non-negative integers) $$ P=<P_1, P_2, ..., P_n> $$, where the prices $P_i$ appear in non-decreasing order. Moreover, you have access to an oracle that can be queried with an integer $a$ and returns "yes" if and only if $a \le k$ for some unknown integer $k$. Each query to the oracle requires constant time.

The goal is that of finding a subset $S$ of $\{1, \dots,n\}$ such that the quantity $\sigma(S) = \sum_{i \in S} P_i$ is at most $k$ and $\sigma(S)$ is maximized.

Is there a way to solve this problem in $O(n)$ time?

For example, if $$ P=<P_1=3, P_2=5, P_3=10> $$ and the unknown integer $k$ is $16$, the best choice of $S$ is $\{2,3\}$ and $\sigma(S) = 15$.

Improve this question
$\endgroup$
3
  • $\begingroup$ @John19 is $k$ really unkown? If it is, then this question might prove to be way more difficult (since we don't know beforehand how high the sum can go, so we don't know how to restrict ourselves efficiently) $\endgroup$
    – nir shahar
    Jul 3, 2021 at 18:51
  • 1
    $\begingroup$ Sounds exactly like the subset sum problem, except for the unknown $k$, but that's a trivial reduction from one problem to the other. This variant is NP-hard, i.e. no known polynomial time algorithm for the general case, never mind an O(n) algorithm. Assuming you got this problem from somewhere, are you sure you included all the constraints and used the same wording? For example, a polynomial time algorithm might exist if there were some restriction on the input or if it were "subarray" instead of "subset". $\endgroup$
    – Bernhard Barker
    Jul 4, 2021 at 6:21
  • 1
    $\begingroup$ What's the context where you encountered this problem? Can you link to or credit the original source? $\endgroup$
    – D.W. ♦
    Jul 5, 2021 at 7:06

1 Answer 1

Reset to default
4
$\begingroup$

There is no polynomial-time algorithm for your problem, unless $\mathsf{P}=\mathsf{NP}$.

Suppose that such an algorithm $A$ exists. Then we can use $A$ to solve the subset-sum problem (which is known to be $\mathsf{NP}$-complete) in polynomial time. Let $\langle X, t\rangle$ be an instance of subset-sum where $X = \langle X_1, \dots, X_n\rangle$ is a collection of integers and $t$ is the target integer.

We pick $P=X$ and $k=t$ and implement the oracle that decides whether $a \le k$ in the straightforward way. Then we simulate $A$ on input $P$ using the above oracle to compute $\sigma(S)$ in polynomial time.

If there exists a subset of $X$ of total sum $t$, then clearly the returned set $S$ is such that $\sigma(S)=t$. If there is no such subset of $X$, then all choices of $S' \subseteq \{1, \dots, n\}$ are such that $\sigma(S')$ is either strictly smaller or strictly larger than $t$. This shows that the returned set $S$ satisfies $\sigma(S) < t$.

We then answer "yes" to the subset sum instance if and only if $\sigma(S) = t$.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Should a* be sigma? Also mentioning that subset-sum is NP complete might be helpful. $\endgroup$
    – idmean
    Jul 4, 2021 at 7:06
  • $\begingroup$ @idmean I guess a* here is $S$ $\endgroup$
    – justhalf
    Jul 4, 2021 at 8:51
  • $\begingroup$ @idmean, thank you! A previous edit of the question was concerned with finding only the value $\sigma(S)$, which was called $a^*$. I edited the answer to match the new question notation but I missed that occurrence of $a^*$. $\endgroup$
    – Steven
    Jul 4, 2021 at 9:09

Your Answer

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

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