  We consider the 0-1 Penalized Knapsack Problem (PKP). Each item has a profit,
a weight and a penalty and the goal is to maximize the sum of the profits minus
the greatest penalty value of the items included in a solution. We propose an
exact approach relying on a procedure which narrows the relevant range of
penalties, on the identification of a core problem and on dynamic programming.
The proposed approach turns out to be very effective in solving hard instances
of PKP and compares favorably both to commercial solver CPLEX 12.5 applied to
the ILP formulation of the problem and to the best available exact algorithm in
the literature. Then we present a general inapproximability result and
investigate several relevant special cases which permit fully polynomial time
approximation schemes (FPTASs).
