# Knapsack up to the heaviest item

There are $$n$$ items with weights $$w_1,\ldots,w_n$$ and values $$v_1,\ldots,v_n$$. There is a knapsack with capacity $$W$$. A subset of items is called feasible up to heaviest item if, once the heaviest item is removed from the subset, the weight of the remaining set is at most $$W$$. The knapsack up to heaviest item problem is to find a subset that maximizes the total value subject to being feasible up to one item.

I was trying to solve this problem, and I think I found that it is NP-hard - by reduction to standard knapsack problem. Given a standard knapsack problem, construct a knapsack-up-to-heaviest-item problem as follows.

• There are $$n+1$$ items: the $$n$$ items in the original problem, plus one "big item".
• The big item has value $$v_B > \sum_{i=1}^n v_i$$ and weight $$w_B > \sum_{i=1}^n w_i$$.
• The size of the new knapsack is $$W+w_B$$.

In the new problem, any optimal solution must contain the big item, since if it does not contain the big item, the sum of weights in the knapsack is less than $$W+w_B$$, so the big item can be added and the solution is still feasible. Moreover, in any optimal solution, the heaviest item is the big item. Hence, once the big item is in the knapsack, the problem is equivalent to the original knapsack problem.

My questions:

• Has this problems been studied before?
• Is my hardness proof correct?