Knapsack with non-trivial "utility" function

Question

The standard knapsack problem imagines a thief trying to stick the most items in his knapsack as possible. It assumes that having, say, two Picasso paintings is twice as good as having one.

We might extend this problem by noting that people have diminishing returns, i.e. two Xs are not twice as good as one X. For example, maybe we think that the utility of having $n$ items is $\log n$ times as good as having one.

Is this a known problem? I didn't see it in Wikipedia's list of knapsack problems. It seems like it should be NP-Hard, but I'm having trouble proving a reduction.

EDIT: As some examples, we could consider $u(x)=0$ in which case there's a constant-time solution to maximize. We could also consider $u(S)=|\{x\in S: \textbf{x is the encoding of a TM that halts}\}|$ in which case maximizing the utility isn't even computable.

So changing the the function to maximize has a dramatic effect on the solubility of knapsack. Can we make a claim like "If $f$ is a non-constant, computable function, then maximizing $f$ in a knapsack is NP-Hard?"

Answer 1

EDIT: It turns out this is actually a very well studied problem if you know the terms to search for. Rather than calling it a utility function with diminishing returns, you need to look for maximization of submodular functions. E.g. Non-monotone submodular maximization under matroid and knapsack constraints. And it turns out that it is NP-Hard.

---

I have thought about this some more and I have come to some conclusions.

First, I asked "If $u$ is a non-constant, computable function, then is maximizing $u$ in a knapsack NP-Hard?" The answer is no. For example,

$u(X) = \left\{ \begin{array}{lr} \sum_{x\in X} x & \textrm{all }x_i\textrm{ are the same}\\ 0 & \textrm{otherwise} \end{array} \right.$

can be maximized in linear time (just try $1,...,n$ copies of each item and see which is maximal).

However, I did find a reduction for a large class of utility functions. If the utility function $u$ obeys:

1. $u(X\cup Y)=u(X)+u(Y)$ if $X\cap Y = \emptyset$ (independence / no substitute goods)
2. $u(\{x,x\})<2u(\{x\})$ (diminishing returns)
3. You can specify the utility of a single item as an input (similar to normal knapsack)

Then the following reduction works. Suppose $S=\{(w_1, v_1),\dots,(w_n, v_n)\}$ is the set of things that you want to put into your knapsack, and you have an oracle to solve a utility knapsack using a function that meets those three criteria. You can create $S'$ by taking each $(w_i, v_i)$ and creating copies $(w_i,v_i),(2w_i, 2v_i),...$ until you reach the weight limit. Put all these copies into $S'$. Provide $S'$ to the utility knapsack solver, which we can do because of (3).

The resulting solution won't have any duplicate items (by (2)), and so by (1) its utility is the same as its value in the normal knapsack. So I think it will be the solution to normal knapsack as well.

Answer 2

Assuming that the added value becomes zero after a constant number of copies (i.e r, r+1, r+2, etc copies are all valued the same),

This can be considered the multiple choice knapsack (given on your list): Given $k$ groups of items, we can pick exactly one from each group.

Each group will contain copies of the item.

To take your example, a group will contain 1 Picasso painting value at $v_1$, 2 paintings valued at $v_2$ where $v_2 \lt 2v_1$ etc.

If you allow unbounded items to picked, then you need to specify exactly how the set of values (i.e. how much are $k$ paintings worth) is an input.