0
$\begingroup$

I wonder if the knapsack problem with diminishing prices is already studied? The problem is similar to the regular knapsack problem, except the price of each item is a decreasing function of the total size of the already selected items.

Given $n$ items each with size $s_i$ and price $v_i(s)$, where $s$ is the total size of the already selected items, a size limit $S$ and a total price $V$, we want to find a sequence of items $\langle e_1,\cdots,e_k \rangle$ so that $\sum_{i=1}^k s_{e_i} \le S$ and $\sum_{i=1}^k v_{e_i}(\sum_{j=1}^{i-1}s_{e_j})\ge V$.

The problem is obviously at least as hard as the regular Knapsack problem (i.e., weakly NP-hard). I wonder if the problem is any harder? Can the dynamic programming solution for the regular problem be used for this problem as well.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ What exactly do you want to know? Seems obvious it is at least as hard as the standard knapsack, so it is NP-hard -- imagine the case where each $v_i$ is a constant function. Also, it's not clear how you plan to specify the functions $v_i$. If they are specified via a truth table, they take exponential space to specify (hence the running time of standard algorithms might become polynomial in the input size). $\endgroup$
    – D.W. ♦
    Mar 26, 2018 at 3:50
  • $\begingroup$ True! It is at least as hard, but I wonder if it is harder at all? i.e., is there any reason the standard dynamic algorithm for knapsack does not produce the optimal answer. In my case, the function $v_i(\cdot)$ can be expressed in constant size. It is actually $1$ minus a sigmoidal function. $\endgroup$
    – Helium
    Mar 26, 2018 at 4:15
  • $\begingroup$ Please edit the question to ask the question you want answered. Right now I don't see an answerable technical question. If you want to ask whether it is harder, please edit the question to ask that, and define what counts as harder for you. Are you asking whether it is in NP? If you just want to know whether the standard dynamic programming algorithm works, what have you tried? Have you tried it on some examples? Have you tried writing down pseudocode? Have you tried to prove it correct? You should spend some time on this yourself before asking here. $\endgroup$
    – D.W. ♦
    Mar 26, 2018 at 6:46

1 Answer 1

Reset to default
1
$\begingroup$

Consider the special case where $V_i\le v_i(s)< V_i+\epsilon$ such that $\epsilon$ is a very small positive constant, then your problem is equivalent to the regular knapsack problem where item $i$ has price/value $V_i$. So your problem is still NP-hard.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I think it is pretty obvious that the problem is at least as hard as regular Knapsack (weakly np-hard) since it is a generalization of Knapsack. My question is mostly about if this problem is any harder (e.g., strongly np-hard). It seems to me that this problem still can be solved using the regular dynamic programming technique used to solve original Knapsack. $\endgroup$
    – Helium
    Jul 1, 2018 at 17:02
  • $\begingroup$ @Helium, as I mentioned before, you should be editing your post to articulate the question clearly in the post itself. That's a fine question but that question doesn't appear anywhere in the post itself. $\endgroup$
    – D.W. ♦
    Jul 1, 2018 at 18:50
  • $\begingroup$ @D.W. I updated the question. I hope it is clearer now. $\endgroup$
    – Helium
    Jul 15, 2018 at 16:43

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.