Search code examples
definitionknapsack-problemsubset-sum

Correct definition of The Subset Sum Problem

Reading the book Knapsack Problems, 2004 edition, by Hans Kellerer, Ulrich Pferschy and David Pisinger, about the subset sum problem, I found this definition (Chapter 4):

Given a set N = {1, ... , n} of n items with positive integer weights W1, ... , Wn and a capacity c, the subset sum problem (SSP) is to find a subset of N such that the corresponding total weight is maximized without exceeding the capacity c.

formally found in Section 2.1 as (sorry, no LaTeX support)

enter image description here

Looking for pseudo-code samples I found this wikipedia article, where a totally different, albeit informal, definition is stated:

given a set (or multiset) of integers, is there a non-empty subset whose sum is zero?

Although, it also says There are several equivalent formulations of the problem, I don't believe this one and the book's can be called equivalent at all.

Am I looking at two different problems here, thinking it's the same? What am I missing?

Thanks

Solution

  • You are right, these two definitions are not equal. The definition inside Knapsack Problems describes an optimization problem. In this case it is a NP-Hard problem. The definition on wikipedia describes an existence problem. This is NP-Complete.

    One big difference between both definitions is the verification of the correctness.

    • The existence problem can easily verified in linear time. Sum the solution and check whether it is 0.
    • The verification of the optimization is hard. Is the calculated solution really the best one, or is there a better one?