0
$\begingroup$

Suppose $P\neq NP$. The following problem can be solved in polynomial time?

  • Given natural number $n$ and positive real numbers $a_1,a_2,\dots,a_n$ and $b_1,b_2,\dots,b_n$. The goal is to find $I\subseteq\{1,2,\dots,n\}$ such that $\sum_{i\in I}b_i$ maximized and $\sum_{i\in I}a_i\leq 5$.

But I have no idea about it. Any help will be appreciated and I prefer to get some hints, not the complete solution.

Improve this question
$\endgroup$
4
  • $\begingroup$ If you only want to ask about the first problem, I suggest that you edit your question to ask only about the first problem. There is no need to list a problem that you are not asking about and where you already know the answer. Also, please add a credit to the original source that you are copying from, as per cs.stackexchange.com/help/referencing. Where you write "Give", do you mean "Given"? How are the real numbers represented? $P,NP$ relate to problems on bits, not real numbers. $\endgroup$
    – D.W. ♦
    Commented Dec 4, 2023 at 5:47
  • $\begingroup$ Oh, it looks like the question has already been answered previously. I've marked it as a duplicate of the prior question, where you should be able to find an answer to the question. $\endgroup$
    – D.W. ♦
    Commented Dec 4, 2023 at 5:50
  • $\begingroup$ What condition for the a_i would make it polynomial time? $\endgroup$
    – gnasher729
    Commented Dec 4, 2023 at 8:01
  • $\begingroup$ @gnasher729 I edit it. I think it's polynomial due to this problem is knapsack and due to $W=O(1)$ the running time will be $O(n)$ with dynamic programming. $\endgroup$
    – ErroR
    Commented Dec 7, 2023 at 8:57

0

Reset to default

Browse other questions tagged or ask your own question.