There is a finite set of numbers $M$. For every subset $X\subseteq M$, define $s(X)$ as the sum of numbers in $M$.
A price-vector is a function $p: M\to (0,1)$ assigning a price to each element of $M$, such that the total price of all elements of $M$ is $1$: $p(M)=1$.
In a knapsack problem, there is a budget $b\in(0,1)$ and a price-vector $p$, and the goal is to find a subset $X \subseteq M$ with a total price of at most $b$ and a maximum sum, i.e.:
\begin{align*} \operatorname{best}(M,b,p) := \arg \max_{X\subseteq M, ~~~p(X)\leq b} s(X) \end{align*}
In an inverse-knapsack problem, there is a budget $b\in(0,1)$ and a bundle $X$, and the goal is to find a price-vector $p$ such that $X\in \operatorname{best}(M,b,p)$.
For example, suppose $M = \{1,2,4,100\}$ and $b = 0.7$:
- For the set $X_1 = \{100\}$, we can take $p_1 = (0.1,0.1,0.1,0.7)$, since $p_1(X_1)=0.7$ and $s(X_1)=100$ and all subsets with a higher sum cost at least $0.8$.
- For the set $X_2 = \{1,2,4\}$, we can take $p_2 = (0.01,0.01,0.01,0.97)$, since $p_2(X_2) < b$ and $s(X_2)=7$ and all subsets with a higher sum cost at least $0.97$.
- For the set $X_3 = \{1,2\}$, there is no corresponding price, since $s(X_3)=3$, and for any price-vector $p$, either $p(4)\leq 0.5$ or $p(100)\leq 0.5$, so there is at least one affordable subset with a sum higher than $3$.
There are many interesting questions to ask about this inverse-knapsack problem, but I am interested in the following one: suppose that, for some $p$, we found an $X\in \operatorname{best}(M,b,p)$. Now, we are given some $Y$ with $s(Y)>s(X)$. Does there exist a price-vector $q$ such that $Y\in \operatorname{best}(M,b,q)$?
I can prove that the answer is "yes" if $Y$ is a singleton, $Y = \{y\}$. Proof: Since $X\in \operatorname{best}(M,b,p)$, and $s(Y)>s(X)$, we must have $p(Y)>b$. Define the price-vector $q$ as follows:
- $q(y) = b$
- For all $x\neq y$: $q(x) = p(x)\cdot \frac{1-b}{1-p(Y)}$
$q$ is a price-vector, since $q(M) = q(Y) + q(M\setminus Y) = b + (1-b) = 1$. To prove that $Y\in \operatorname{best}(M,b,q)$, we assume that there is some other subset $Z$ with $s(Z) > s(Y)$, and prove that $q(Z) > q(Y)$. There are two cases:
- If $Z$ contains $y$, then certainly $q(Z)>q(y) = b$.
- If $Z$ does not contain $y$, then $q(Z) = p(Z)\cdot \frac{1-b}{1-p(Y)} > p(Z)$, since $p(Y)>b$. Moreover, $s(Z)>s(Y)>s(X)$, so $p(Z)>b$. Hence $q(Z)>b$ too.
Is the same true for any $Y$?