<p>NOTE: My original reduction didn't work. Fixed now.</p>

<p>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$. </p>

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

CC BY-SA 3.0
2016-04-11T14:19:40.990Z
2016-04-11T23:06:57.657Z
2016-04-11T23:06:57.657Z
Peter Shor 
<p>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:</p>

<ol>
<li><p>$\sum_{i=1}^{n} \alpha_iw_ix_i\leq W$</p></li>
<li><p>$0 \leq \alpha _i \leq 1$</p></li>
<li><p>$\alpha_iv_iw_ix_i \geq p_i x_i $</p></li>
</ol>

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

<p>Is this problem NP-hard?</p>

<p>(Credit for this question goes to the author of the reddit post at <a href="https://www.reddit.com/r/compsci/comments/4e7q9t/polynomialtime_algorithm_for_modified_knapsack/" rel="nofollow">https://www.reddit.com/r/compsci/comments/4e7q9t/polynomialtime_algorithm_for_modified_knapsack/</a>).</p>

CC BY-SA 3.0
2016-04-11T04:02:56.433Z
If you let $y_i = \alpha_i w_i$, make all the substitutions, the presentation would be simpler.
Chao Xu
CC BY-SA 3.0
2016-04-11T07:11:03.913Z
Isn't enough to pick $p_i = 0$ to reduce the problem to Knapsack?
Marzio De Biasi
CC BY-SA 3.0
2016-04-11T07:16:50.927Z
@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)
aellab
CC BY-SA 3.0
2016-04-11T07:38:01.670Z
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?)
Marzio De Biasi
CC BY-SA 3.0
2016-04-11T08:50:54.993Z
@Michael: Can you confirm that the alternative definition of the problem that comes with less clutter given at https://www.reddit.com/r/compsci/comments/4e7q9t/polynomialtime_algorithm_for_modified_knapsack/d1xuubl is equivalent to yours? If so, it seems easy to show that the problem is NP-hard and in particular NP-complete.
Christoph Haase
CC BY-SA 3.0
2016-04-11T10:12:03.893Z
@ChristophHaase Yeah, that reduction seems equivalent. Why is it easy?
aellab
<cc.complexity-theory><optimization><linear-programming><integer-programming>
Is finding an optimal solution to this Knapsack-like problem NP-hard?
aellab
# Is finding an optimal solution to this Knapsack-like problem NP-hard?

(Asked by: username_0 on 2016-04-11)

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

**Tags:** cc.complexity-theory, optimization, linear-programming, integer-programming
> **Comments:**
> **username_1**: If you let $y_i = \alpha_i w_i$, make all the substitutions, the presentation would be simpler.  
> **username_2**: Isn't enough to pick $p_i = 0$ to reduce the problem to Knapsack?  
> **username_0**: @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)  
> **username_2**: 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?)  
> **username_3**: @Michael: Can you confirm that the alternative definition of the problem that comes with less clutter given at https://www.reddit.com/r/compsci/comments/4e7q9t/polynomialtime_algorithm_for_modified_knapsack/d1xuubl is equivalent to yours? If so, it seems easy to show that the problem is NP-hard and in particular NP-complete.  
> **username_0**: @ChristophHaase Yeah, that reduction seems equivalent. Why is it easy?  

---

## 1 answers

### Answer by username_4 on 2016-04-11. Score: 7 | Accepted answer

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.


---

