Is finding an optimal solution to this Knapsack-like problem NP-hard?
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 &lt; 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.