Knapsack Problem - Variations - Subset-sum Problem

Subset-sum Problem

The subset sum problem, is a special case of the decision and 0-1 problems where each kind of item, the weight equals the value: . In the field of cryptography, the term knapsack problem is often used to refer specifically to the subset sum problem and is commonly known as one of Karp's 21 NP-complete problems.

The generalization of subset-sum problem is called multiple subset-sum problem, in which multiple bins exist with the same capacity. It has been shown that the generalization does not have an FPTAS.

Read more about this topic:  Knapsack Problem, Variations

Famous quotes containing the word problem:

    The great problem of American life [is] the riddle of authority: the difficulty of finding a way, within a liberal and individualistic social order, of living in harmonious and consecrated submission to something larger than oneself.... A yearning for self-transcendence and submission to authority [is] as deeply rooted as the lure of individual liberation.
    Wilfred M. McClay, educator, author. The Masterless: Self and Society in Modern America, p. 4, University of North Carolina Press (1994)