# Is finding an optimal solution to this Knapsack-like problem NP-hard?

Suppose our inputs are a set of objects with weights $w_1,...,w_n$. We have two separate sets of profits: $p_1,...,p_n$ and $v_1,...,v_n$. We wish to maximize $\sum_{i=1}^{n} p_i(1-x_i)+\alpha_i v_iw_ix_i$ such that $x_i \in \{0,1\}$ subject to:

1. $\sum_{i=1}^{n} \alpha_iw_ix_i\leq W$

2. $0 \leq \alpha _i \leq 1$

3. $\alpha_iv_iw_ix_i \geq p_i x_i$

In other words, we can sell any amount of whole objects at profit $p_i$, and some subset of object fractions whose weight does not exceed $W$ at price $v_i$ (but then we can't sell the remaining fractions of those objects).

Is this problem NP-hard?

(Credit for this question goes to the author of the reddit post at https://www.reddit.com/r/compsci/comments/4e7q9t/polynomialtime_algorithm_for_modified_knapsack/).

• If you let $y_i = \alpha_i w_i$, make all the substitutions, the presentation would be simpler. Apr 11, 2016 at 4:02
• Isn't enough to pick $p_i = 0$ to reduce the problem to Knapsack? Apr 11, 2016 at 7:11
• @MarzioDeBiasi No, since you've then reduced the problem to Fractional Knapsack, which has a polynomial-time greedy solution (sort the items by value divided by weight)
– mich
Apr 11, 2016 at 7:16
• Ah ok, you can split the pieces before carrying them to the next town (I read the linked reddit post :-) Did you try the greedy algorithm on a few instances of your problem? (did you find an instance in which the greedy algorithm doesn't work?) Apr 11, 2016 at 7:38
• @Michael: Can you confirm that the alternative definition of the problem that comes with less clutter given at reddit.com/r/compsci/comments/4e7q9t/… is equivalent to yours? If so, it seems easy to show that the problem is NP-hard and in particular NP-complete. Apr 11, 2016 at 8:50

Can't subset-sum be reduced to this problem fairly easily? Suppose all the profits $v_i$ are the same, say $v_i = 1$, and all the profits $p_i$ are proportional to the weights, so $p_i = \beta w_i$ with $\beta < 1$.
Now, if there's a set of weights $S$ such that $\sum_{i\in S} w_i = W$, you can get a profit of $$\sum_{i \in S} w_i + \sum_{i \not\in S} p_i = W + \beta \left(\sum_i w_i -W\right) = (1-\beta)W + \beta \sum_i w_i,$$ which is optimal. If there's not such a set of weights, then we can't.