Two versions of Subset Sum Problem

Question

I keep seeing two versions of the Subset Sum Problem. The first and seemingly least common is:

Given an integer bound $W$ and a collection of $n$ items, each with a positive integer weight $w_i$, find the subset $S$ of the items that maximizes $\sum_{i \in S} w_i$ while keeping this sum at most $W$. Or the decision version: Is there a subset obeying the at-most-$W$ rule with weight at least some number $k$.

So just Knapsack except the values are the weights themselves.

The second and seemingly more common is:

Given a set of $n$ integers, is there a non-empty subset whose sum is 0 (or equivalently, some number $k$)?

E.g., my textbook (Kleinberg and Tardos) as well as this have the first one. Wikipedia and other websites have the second.

I believe both are NP-complete. That said, I haven't found an "obvious reduction" from one to the other that suggests why the two problems are given the same name. So my questions are:

1. Do quick reductions exists between the two?
2. Why are these given the same name in the first place?

Answer 1

Given an instance of the second problem, we can easily reduce it to an instance of the (decision version of) the first problem: simply take $W = k$. There is a subset of sum at least $k$ and at most $W$ iff there is a subset of sum exactly $k$.

In the other direction, the idea is to add to the collection a small set of items satisfying the following two properties:

• The total weight of the new items is $W-k$.
• Every weight between $0$ and $W-k$ can be represented as a sum of a subset of the new items.

Having added this collection, we ask whether there is a subset summing to exactly $W$. It is not hard to check that there is a subset of the original collection whose sum is between $k$ and $W-k$ if there is a subset of the enlarged collection summing to $W$ exactly.

How do we add these items? The simplest case is when $W - k = 2^t$, in which case we can simply add $1,2,4,\ldots,2^{t-1}$. More generally, suppose $2^t \leq W-k < 2^{t+1}$, and let $W-k = 2^t + C$. We then add $1,2,4,\ldots,2^{t-1},C$.