Two versions of Subset Sum Problem 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:


Do quick reductions exists between the two?
Why are these given the same name in the first place?
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 &lt; 2^{t+1}$, and let $W-k = 2^t + C$. We then add $1,2,4,\ldots,2^{t-1},C$.