Knapsack up to the heaviest item

Question

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?

Answer 1

The problem (are there items such that all except the largest fit, and the total value is ≥ V) is obviously in NP. It is also NP complete because we can use it to solve Knapsack:

Given a knapsack problem, add an item with sufficiently large weight w, and sufficiently large value v, solve the problem with V + v, and the solution with the large item removed is the solution for the knapsack problem.

We can also solve this problem using knapsack: For each item with weight w and value v, solve knapsack removing this item and all items with weight > w and a goal for the value of V - v.