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

Question

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/).

Answer 1

NOTE: My original reduction didn't work. Fixed now.

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.