An extension of Dembo-Hammer's reduction algorithm for the 0-1 knapsack problem

Yang Yang

REVIEW 4 major objections 5 minor 23 references

An extension of Dembo-Hammer's reduction algorithm for the 0-1 knapsack problem

T0 review · 4 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper claims that a 0-1 knapsack instance can be reduced to at most $n^{2i}$ subinstances by extending Dembo-Hammer reduction, leaving only a thin band of uncertain items around the break item.

desk verdict Theorems 2 and 3 are a genuine but modest generalization of Dembo-Hammer's reduction, yet the O(n^{2i}) exact-resolution claim rests on an unstated Lemma 1 that cannot exist given the paper's own concession that the residual subproblem is NP-hard. read the letter →

arxiv 2506.06138 v1 pith:WDBQP5LN submitted 2025-06-06 cs.CC cs.DS

Yang Yang This is my paper

classification cs.CCcs.DS MSC 90C2790C1068Q25

keywords 0-1knapsackproblemreductionalgorithmDembo-HammerbreakitemcoreNP-hardnesssearchtreeCPLEX

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proposes EDHR, an extension of Dembo and Hammer's reduction algorithm for the 0-1 knapsack problem. The idea is to leave a thin band of items around the break item unresolved: at most $i-1$ items on the high-density side can be missing from an optimal solution, and at most $i-1$ items on the low-density side can be present. Enumerating these few exceptions reduces an $n$-item instance to at most $n^{2i}$ subinstances, so a practitioner who sets $i=2$ gets $O(n^2)$ subinstances. The author reports experiments on randomly generated instances showing that this preprocessing, run before CPLEX, reduces CPLEX's search-tree size by roughly half for uncorrelated and strongly correlated data and by smaller amounts for other families. The value of the claim, if correct, is a tunable polynomial-time reduction that turns most of the knapsack problem into fixed decisions and leaves only a small core to be searched.

What carries the argument

The load-bearing object is the five-set partition generated by the break item $b$, the residual capacity $r = C - \sum_{j<b} w_j$, and the integer $i$. The set $N_{i,1}$ collects high-density items whose density stays above $p_b/w_b$ even when their weight is inflated by $r/i$, and $N_{i,4}$ collects low-density items whose density stays below $p_b/w_b$ even when their weight is deflated by $r/i$; the middle sets $N_{i,2}$, $N_{i,3}$, $N_{i,5}$ hold everything else. Theorems 2 and 3 are proved by a counting argument: if too many $N_{i,1}$ items were missing, the compensating profits from $N_{i,4}$ and $N_{i,5}$ items would have to have a higher average density than the missing items can supply, contradicting optimality. This conversion of an intractable search over all $2^n$ subsets into an enumeration over thin exceptional layers is what carries the reduction.

What would settle it

Take a random instance with $n=200$, set $i=2$, compute $N_{2,1}$ as defined in the paper, and use an independent exact solver to enumerate all optimal solutions; if two or more items of $N_{2,1}$ are missing from every optimal solution, Theorem 2 is false and the reduction bound collapses.

Watch

Extended reading notes

Core claim

The central claim is Theorem 2 plus Theorem 3: after ordering items by profit density and locating the break item $b$ with residual capacity $r$, define the partition $N_{i,1}, \ldots, N_{i,5}$ via the adjusted ratio tests $p_j/(w_j+r/i) > p_b/w_b$ and $p_j/(w_j-r/i) < p_b/w_b$. Then $N_{i,1}$ contains at most $i-1$ items that are not chosen in an optimal solution, and $N_{i,4}$ contains at most $i-1$ items that are chosen. The proof combines the Dantzig bound, the break solution as a lower bound, and a double-counting comparison of the profit lost from missing $N_{i,1}$ items against the profit gained from extra $N_{i,4}$ and $N_{i,5}$ items; Claim 1 bounds the average density of the compensating set. Consequently every optimal solution lies in the family $Y_i$ formed by taking all but at most $i-1$ items of $N_{i,1}$, at most $i-1$ items of $N_{i,4}$, and an optimal solution of the subinstance on $N_{i,2} \cup N_{i,3} \cup N_{i,5}$. The author concludes that the original problem is reduced to at most $n^{2i}$ subinstances and, on the strength of an invoked lemma, that the decision variables on $N_{i,1}$ and $N_{i,4}$ are exactly solvable in $O(n^{2i})$ time. The abstract states the bound as $n^i$, while the body's enumeration argument bounds the family by $n^{2i}$; for $i=2$ both are $O(n^2)$.

Load-bearing premise

EDHR's polynomial-time claim rests on an unstated lemma that the leftover subinstances can be solved quickly; if that lemma does not hold, each of the $n^{2i}$ subinstances is itself an NP-hard knapsack problem, and the claimed $O(n^{2i})$ step is unjustified.

Editorial extensions

If this is right

Setting $i=1$ reproduces Dembo-Hammer's original reduction, so EDHR is a strict generalization with a single tuning parameter.
With $i=2$ the reduction produces at most $O(n^2)$ subinstances, and the paper's experiments show CPLEX ticks drop by 53.88% on uncorrelated, 51.24% on strongly correlated, and 38.05% on almost strongly correlated instances.
If the invoked lemma holds, EDHR gives a polynomial-time preprocessing step that fixes all but a small core of items before an exact solver runs.
The paper's Theorem 4 says the required $i$ has no universal upper bound, so the practical benefit is instance-dependent rather than a uniform worst-case speedup.
The sets $N_{i,1}$ and $N_{i,4}$ can be used to prune search spaces in metaheuristic solvers, as the author lists as future work.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Beyond the paper: the real workload will sit in the subinstances on $N_{i,2} \cup N_{i,3} \cup N_{i,5}$; a fair test of EDHR as a solver would report time spent solving those subinstances, not only the reduction's effect on CPLEX ticks.
Beyond the paper: because Theorem 4 shows no fixed $i$ classifies all density-different items, EDHR is best viewed as a parameterized core-reduction scheme; it could be combined with dynamic programming or branch-and-bound on the middle sets to get a hybrid exact solver.
Beyond the paper: a natural experiment is to measure how often $N_{2,1} \cup N_{2,4}$ is empty on hard benchmark classes; the author's Table 6 suggests such empty cases give zero speedup, so instance generation that maximizes this set would test the algorithm's advertised advantage.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The paper's real content is a modest generalization of Dembo-Hammer's reduction, but the headline complexity claim does not hold up. Theorems 2 and 3, which bound the number of exceptional items in N_{i,1} and N_{i,4} by i-1, are a natural extension of DHR (the i=1 case gives the classic result). The reduction rule itself could be useful as a preprocessing step: enumerate at most n^{2i} candidate subsets of the "hard" items, then solve the residual subproblems. That is a plausible strategy, and the experiments show real tick reductions on several random families, with honest reporting of zero improvement on IC instances.

The soft spots are serious. The O(n^{2i}) exact-resolution claim is supported only by a 'Lemma 1' that is never stated, proved, or cited. The paper itself concedes that the residual subproblem on N_{i,2} ∪ N_{i,3} ∪ N_{i,5} is NP-hard. Therefore no lemma can supply a polynomial-time oracle for each subinstance; the claimed complexity collapses to 'there are at most n^{2i} NP-hard subproblems.' That is a load-bearing flaw, not a technicality.

The proof of Theorem 2 also has unjustified steps. Equation (12) turns an inequality into an equality without comment. Inequality (13) is asserted without derivation, and the direction depends on the sign of Σ_{F_i,3}w − Σ_{F_i,1}w, which is not handled. The abstract says the method reduces to at most n^i subinstances, while Section 3 says n^{2i}; that discrepancy affects the stated complexity. The experiments are not reproducible: no code or data, and the parameter i = 2 is chosen after seeing performance.

Despite these problems, the reduction theorems might be salvageable. If the author supplies complete proofs of Theorems 2 and 3 and drops the polynomial-time resolution claim, replacing it with the actual enumeration count plus the explicit NP-hardness of the residual subproblem, the idea could become a short note. As submitted, the central claim is unsupported and the proof is too unreliable. I would not send this to peer review in its current form; the missing lemma alone is disqualifying. If a revised version appears with a complete proof and a corrected complexity statement, it would deserve review.

Referee Report

4 major / 5 minor

Summary. The paper proposes an extension of Dembo-Hammer's reduction algorithm (EDHR) for the 0-1 knapsack problem. The algorithm partitions the item set N into five subsets N_{i,1},...,N_{i,5} depending on a user-chosen positive integer i and on the break item's profit density. The main structural claims are Theorem 2 (N_{i,1} contains at most i-1 items not in any optimal solution) and Theorem 3 (N_{i,4} contains at most i-1 items in any optimal solution). From these the paper concludes that the optimal solution belongs to a family Y_i of at most n^{2i} candidate solutions, and asserts that, based on a 'Lemma 1', the decisions on N_{i,1} and N_{i,4} can be exactly solved in time O(n^{2i}). The paper reports computational experiments on five randomly generated instance families showing that EDHR with i=2 reduces CPLEX's internal 'ticks' relative to solving the original instance directly, with zero improvement on inverse-strongly-correlated instances.

Significance. If the main complexity claim were correct, the paper would provide a substantial theoretical advance: a reduction of 0-1 KP to a polynomial number of subinstances along with a polynomial-time exact resolution of the decision variables in the 'exceptional' sets. The underlying idea of bounding the number of deviations from the break solution is natural, and the experimental study is transparent in reporting a baseline and in admitting cases (IC instances and literature instances) where the method yields no improvement. However, the central algorithmic claim is not established. The paper makes no machine-checked proofs or reproducible code available, and the key step from the combinatorial bound to the O(n^{2i}) time bound depends on a lemma that never appears. The present manuscript therefore does not support the advertised complexity result.

major comments (4)

[Section 3, paragraph after the definition of Y_i] The sentence 'Based on Lemma 1, although the 0-1 KP is NP-hard, the decision variables of two subsets N_{i,1} and N_{i,4} can be exactly solved in time complexity O(n^{2i})' is the only bridge from the combinatorial bound |Y_i| ≤ n^{2i} to the claimed runtime. Lemma 1 is never stated, proved, or cited anywhere in the manuscript. Without it, the preceding argument only shows that the optimal solution is contained in a family of at most n^{2i} candidate solutions, each obtained by adjoining some N*_{i,1} and N*_{i,4} to an optimal solution of a residual 0-1 KP on N_{i,2}∪N_{i,3}∪N_{i,5}. Since the paper itself states at the end of Section 3 that this residual subproblem 'is still a NP-hard problem', the O(n^{2i}) exact-resolution claim is unsupported. This is a load-bearing gap in the main result.
[Section 3, proof of Theorem 2, equations (12) and (13)] The chain labeled (12) replaces the ratio (Σ_{j∈D_{i,2}} p_j + Σ_{j∈D_{i,3}} p_j)/(Σ_{j∈D_{i,2}} w_j + Σ_{j∈D_{i,3}} w_j) by Σ_{j∈D_{i,1}} p_j/(Σ_{j∈D_{i,1}} w_j + r) with a strict inequality. Claim 1, as stated, gives only a non-strict inequality, and the paper does not establish strictness. Inequality (13), Σ_{j∈F_{i,3}} p_j - Σ_{j∈F_{i,1}} p_j < (Σ_{j∈F_{i,3}} w_j - Σ_{j∈F_{i,1}} w_j) · (ratio), is asserted without derivation. In particular, the derivation of (16) from (14) and (15) multiplies by the quantity Σ_{j∈F_{i,3}} w_j - Σ_{j∈F_{i,1}} w_j, which could be negative, reversing the inequality; the paper does not prove this quantity is nonnegative. These gaps leave the proof of Theorem 2 incomplete, and Theorem 3 relies on it by symmetry.
[Section 3, paragraph starting 'Let n_{i,1}=|N_{i,1}|'] The text states |N_{i,2} ∪ N_{i,3} ∪ N_{i,5}| = n - n_{i,1} - n_{i,2}; by Definition 2 the correct expression is n - n_{i,1} - n_{i,4}. In addition, the abstract and introduction promise a reduction to at most n^i subinstances, while Section 3 obtains the bound |Y_i| ≤ n_{i,1}^i n_{i,4}^i ≤ n^{2i}. For i=1 the actual number of candidate solutions is 1, not n^2, so the stated bounds are inconsistent. This is not merely cosmetic, because the claimed size of the reduction is the paper's central quantitative message.
[Section 3, Theorem 4 and the following paragraph] The statement 'Constant i has no upper bound' is not a formal complexity assertion, and the proof only shows that for any proposed bound m there exists a particular instance in which a specific item q requires i > m to satisfy inequality (8). This does not establish that the residual subproblem is NP-hard; that NP-hardness is already evident from the definition and from the NP-hardness of 0-1 KP. The concluding sentence 'Since constant i has no upper bound, ... the subproblem ... is still a NP-hard problem' is therefore a non sequitur in context. The discussion also conflates the user-fixed algorithmic parameter i with an instance-dependent quantity, which obscures the meaning of the claimed time bound.

minor comments (5)

[Abstract and introduction] The abstract and the introduction state that EDHR reduces an instance to at most n^i subinstances, while Section 3 states n^{2i}; the two quantities should be reconciled, and the parameter i should be defined once in a consistent way.
[Section 3, paragraph after Definition 2] The explanation of inequality (9) says 'the left side of inequality (9) is always negative when w_j < r/i'; this statement is correct only if the intended expression is p_j/(w_j - r/i), but the surrounding notation is ambiguous and the prose 'implies that these items are never selected by the optimal solution, which contradicts the actual scenario' is unclear.
[Section 4] The experimental section does not provide an algorithm pseudocode for EDHR, nor does it state how the candidate subinstances are solved in the reported runs (for example, whether CPLEX is invoked on each reduced subinstance and whether enumeration overhead is counted in the reported 'ticks'). This makes the experimental comparison difficult to reproduce and to interpret.
[Section 4, Table 6] The table header refers to |N_{2,1} ∪ N_{2,4}| while the notation in the text uses N_{i,1} and N_{i,4}; the indexing should be made uniform.
[Introduction, last sentence] The sentence 'Our method also reduces the interval gap of the distances from power of 2 to integer and decreases the complexity of the method given by Dey et al.' is not supported by any result or experiment in the paper; either it should be substantiated or removed.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: Theorems 2 and 3 are derived from the break solution and density inequalities, the n^{2i} bound is a counting argument, and the reported experiments use a user-chosen parameter i rather than a fitted value presented as a prediction. The missing 'Lemma 1' is a proof gap, not a circular step.

full rationale

The paper's central derivation is the bound that N_{i,1} contains at most i-1 items outside the optimal solution (Theorem 2) and, symmetrically, N_{i,4} contains at most i-1 items inside it (Theorem 3). These statements are proved by an exchange argument using the Dantzig bound, the break solution X', residual capacity r, and the density ordering; the sets N_{i,1} and N_{i,4} are defined by explicit inequalities (Definition 2), and Claim 1 provides a density comparison that is not equivalent to the theorem being proved. The bound |Y_i| <= n^{2i} follows by counting subsets of N_{i,1} and N_{i,4}, so it is a combinatorial consequence rather than a renamed input. The parameter i is a user choice, and the experiments set i=2 after observing that larger constraint sets slow CPLEX; this is mild tuning, but the paper does not present a fitted parameter as an independently predicted quantity. It also reports negative results (IC instances, |N_{2,1} ∪ N_{2,4}| = 0) showing that improvement is not guaranteed by construction. The one serious defect is in Section 3, where the sentence 'Based on Lemma 1, although the 0-1 KP is NP-hard, the decision variables of two subsets N_{i,1} and N_{i,4} can be exactly solved in time complexity O(n^{2i})' invokes a Lemma 1 that is never stated, proved, or cited. That is an omitted proof and an unsupported runtime claim, and it undermines the central complexity conclusion, but it is not circular: the paper does not define Lemma 1 in terms of the target result, and no self-citation is used to close the gap. I therefore find no significant circularity under the definitions used here.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The central claim rests on standard knapsack bounds, the sorting and break-item assumption, and an unstated Lemma 1 that carries the complexity conclusion. No free parameters are fitted to data except the user-chosen i; no invented entities are introduced.

free parameters (1)

i = 2 in experiments
EDHR parameter controlling the r/i thresholds and the allowed number of exceptions. Section 4.1 sets i=2 after 'careful consideration'. The paper claims results for any positive integer i, so i is a user-chosen algorithmic parameter rather than a derived constant.

assumptions (4)

ad hoc to paper Unstated Lemma 1 that enables O(n^{2i}) exact resolution of N_{i,1} and N_{i,4} decision variables.
Invoked in Section 3 but never stated; the central complexity claim depends on it.
standard math The break solution X' and Dantzig bound U are valid lower and upper bounds for 0-1 knapsack.
Used in Theorem 2's inequalities (10) and (11); standard from Dantzig's linear relaxation.
domain assumption Items are sorted by non-increasing profit density, with the break item defined by cumulative weight.
Assumed in Definition 2 and throughout; standard for knapsack reductions.
domain assumption Density orderings imply the profit/weight comparison inequalities in equations (14) and (15).
The proof of Theorem 2 relies on F_{i,3} items having density at least F_{i,1} items and on the average density of F_{i,1} exceeding that of D_{i,2} ∪ D_{i,3}; this follows from sorting and the break-item definitions but is not fully derived in the text.

how reviews work

0 comments

Cite this review

Pith. "Pith review of An extension of Dembo-Hammer's reduction algorithm for the 0-1 knapsack problem." pith.science (2026). https://pith.science/paper/WDBQP5LN

@misc{pith2026250606138,
  author       = {Pith},
  title        = {Pith review of: An extension of Dembo-Hammer's reduction algorithm for the 0-1 knapsack problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WDBQP5LN}},
  note         = {Machine review of arXiv:2506.06138}
}

abstract

Dembo-Hammer's Reduction Algorithm (DHR) is one of the classical algorithms for the 0-1 Knapsack Problem (0-1 KP) and its variants, which reduces an instance of the 0-1 KP to a sub-instance of smaller size with reduction time complexity $O(n)$. We present an extension of DHR (abbreviated as EDHR), which reduces an instance of 0-1 KP to at most $n^i$ sub-instances for any positive integer $i$. In practice, $i$ can be set as needed. In particular, if we choose $i=1$ then EDHR is exactly DHR. Finally, computational experiments on randomly generated data instances demonstrate that EDHR substantially reduces the search tree size compared to CPLEX.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

[1]

Knapsack Problems

Hans Kellerer, Ulrich Pferschy, David Pisinger. Knapsack Problems. Springer- Verlag: Berlin Heidelberg, 2004: 1-548

work page 2004
[2]

A Minimal Algorithm for the 0-1 Knapsack Problem

David Pisinger. A Minimal Algorithm for the 0-1 Knapsack Problem. Operations Research, 1997, 45(5): 758-767. 14

work page 1997
[3]

An Algorithm for Large Zero-One Knapsack Problems

Egon Balas, Eitan Zemel. An Algorithm for Large Zero-One Knapsack Problems. Operations Research, 1980, 28(5): 1130-1154

work page 1980
[4]

Dynamic programming

Richard Bellman. Dynamic programming. Princeton University Press, Princeton, 1957: 1-342

work page 1957
[5]

Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem

Silvano Martello, David Pisinger, Paolo Toth. Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem. Management Science,1999,45(3): 414-424

work page 1999
[6]

New trends in exact algorithms for the 0-1 knapsack problem

Silvano Martello,David Pisinger,Paolo Toth. New trends in exact algorithms for the 0-1 knapsack problem. European Journal of Operational Research, 2000, 123(2): 325-332

work page 2000
[7]

Dembo, Peter Ladislaw Hammer

Ron S. Dembo, Peter Ladislaw Hammer. A reduction algorithm for knapsack problems. Methods of Operations Research, 1980, 36(1): 49-60

work page 1980
[8]

An expanding-core algorithm for the exact 0-1 knapsack problem

David Pisinger. An expanding-core algorithm for the exact 0-1 knapsack problem. European Journal of Operational Research, 1995, 87(1): 175-187

work page 1995

Show all 23 references

[9]

Computer and Intractablility: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, CA, 1979: 1-338

Michael Randolph Garey, David Stifler Johnson. Computer and Intractablility: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, CA, 1979: 1-338

1979
[10]

Reducibility among Combinatorial Problems

Richard Manning Karp. Reducibility among Combinatorial Problems. In: Miller R.E., Thatcher J.W., Bohlinger J.D. (eds) Complexity of Computer Computa- tions. The IBM Research Symposia Series. Springer, Boston, MA, 1972

1972
[11]

Tolerance analysis for 0-1 knapsack problems

David Pisinger, Alima Saidi. Tolerance analysis for 0-1 knapsack problems. European Journal of Operational Research, 2016, 258: 866-876

2016
[12]

Heuristic approaches for the two- and three- dimensional knapsack packing problem

Jens Egeblad, David Pisinger. Heuristic approaches for the two- and three- dimensional knapsack packing problem. Computers & Operations Research, 2009, 36: 1026-1049

2009
[13]

QoS-aware service eval- uation and selection

Dimitrios Tsesmetzis, Ioanna Roussaki, Efstathios Sykas. QoS-aware service eval- uation and selection. European Journal of Operational Research, 2008, 191: 1101-1112

2008
[14]

Ingargiola, James F

Giorgio P. Ingargiola, James F. Korsh. Reduction Algorithm for Zero-One Single Knapsack Problems. Management Science, 1973, 20: 460-463

1973
[15]

A New Algorithm for the 0-1 Knapsack Problem

Silvano Martello, Paolo Toth. A New Algorithm for the 0-1 Knapsack Problem. Management Science, 1988, 34(5): 633-644

1988
[16]

Knapsack Problems: Algorithms and Computer Implementations

Silvano Martello, Paolo Toth. Knapsack Problems: Algorithms and Computer Implementations. Wiley, Chichester, UK, 1990. 15

1990
[17]

Cost Based Filtering for the Constrained Knapsack Problem

Torsten Fahle, Meinolf Sellmann. Cost Based Filtering for the Constrained Knapsack Problem. Annals of Operations Research, 2002, 115(1-4): 73-93

2002
[18]

George B. Dantzig. Discrete-Variable Extremum Problems. Operations Research, 1957, 5(2): 266-288

1957
[19]

Dey, Yatharth Dubey, Marco Molinaro

Santanu S. Dey, Yatharth Dubey, Marco Molinaro. Branch-and-bound solves random binary IPs in poly(n)-time. Mathematical Programming, 2023, 200: 569-587

2023
[20]

Where are the hard knapsack problems ? Computers & Opera- tions Research, 2005, 32: 2271-2284

David Pisinger. Where are the hard knapsack problems ? Computers & Opera- tions Research, 2005, 32: 2271-2284

2005
[21]

YALMIP: A Toolbox for Modeling and Optimization in MAT- LAB

L¨ ofberg Johan. YALMIP: A Toolbox for Modeling and Optimization in MAT- LAB. InProceedings of the CACSD Conference, Taipei, China, 2004

2004
[22]

Iterated two-phase local search for the Set-Union Knapsack Problem

Wei Zequn, Hao Jin-Kao. Iterated two-phase local search for the Set-Union Knapsack Problem. Future Generation Computer Systems, 2019, 101: 1005-1017

2019
[23]

A New Class of Hard Problem Instances for the 0-1 Knapsack Problem

Jorik Jooken, Pieter Leyman, Patrick De Causmaecker. A New Class of Hard Problem Instances for the 0-1 Knapsack Problem. European Journal of Opera- tional Research, 2022, 301(3): 841-854. 16

2022

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Knapsack Problems

Hans Kellerer, Ulrich Pferschy, David Pisinger. Knapsack Problems. Springer- Verlag: Berlin Heidelberg, 2004: 1-548

work page 2004

[2] [2]

A Minimal Algorithm for the 0-1 Knapsack Problem

David Pisinger. A Minimal Algorithm for the 0-1 Knapsack Problem. Operations Research, 1997, 45(5): 758-767. 14

work page 1997

[3] [3]

An Algorithm for Large Zero-One Knapsack Problems

Egon Balas, Eitan Zemel. An Algorithm for Large Zero-One Knapsack Problems. Operations Research, 1980, 28(5): 1130-1154

work page 1980

[4] [4]

Dynamic programming

Richard Bellman. Dynamic programming. Princeton University Press, Princeton, 1957: 1-342

work page 1957

[5] [5]

Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem

Silvano Martello, David Pisinger, Paolo Toth. Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem. Management Science,1999,45(3): 414-424

work page 1999

[6] [6]

New trends in exact algorithms for the 0-1 knapsack problem

Silvano Martello,David Pisinger,Paolo Toth. New trends in exact algorithms for the 0-1 knapsack problem. European Journal of Operational Research, 2000, 123(2): 325-332

work page 2000

[7] [7]

Dembo, Peter Ladislaw Hammer

Ron S. Dembo, Peter Ladislaw Hammer. A reduction algorithm for knapsack problems. Methods of Operations Research, 1980, 36(1): 49-60

work page 1980

[8] [8]

An expanding-core algorithm for the exact 0-1 knapsack problem

David Pisinger. An expanding-core algorithm for the exact 0-1 knapsack problem. European Journal of Operational Research, 1995, 87(1): 175-187

work page 1995