# Knapsack problem with diminishing prices

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.

• 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). – D.W. Mar 26 '18 at 3:50
• 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. – Helium Mar 26 '18 at 4:15
• 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. – D.W. Mar 26 '18 at 6:46

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.