Dynamic programming algorithms for the zero-one knapsack problem. (English) Zbl 0431.90076


90C39 Dynamic programming
65K05 Numerical mathematical programming methods
90C09 Boolean programming


Zbl 0419.90079
Full Text: DOI


[1] Ahrens, J. H., Finke, G.: Merging and sorting applied to the zero-one Knapsack problem. Operations Research23 (1975). · Zbl 0324.90047
[2] Barr, R. S., Ross, G. T.: A linked list data structure for a binary Knapsack algorithm. Research Report CCS 232, Centre for Cybernetic Studies, University of Texas (1975).
[3] Greenberg, H., Hegerich, R. L.: A branch search algorithm for the Knapsack problem. Management Science16 (1970). · Zbl 0191.48401
[4] Horowitz, E., Sahni, S.: Computing partitions with applications to the Knapsack problem. J. ACM21 (1974). · Zbl 0329.90046
[5] Ingargiola, G. P., Korsh, J. F.: A reduction algorithm for zero-one single Knapsack problems. Management Science20 (1973). · Zbl 0304.90082
[6] Kolesar, P. J.: A branch and bound algorithm for the Knapsack problem. Management Science13 (1967).
[7] Magazine, M., Nemhauser, G., Trotter, L.: When the greedy solution solves a class of Knapsack problems. Operations Research23 (19750. · Zbl 0305.90039
[8] Martello, S., Toth, P.: An upper bound for ther zero-one Knapsack problem and a branch and bound algorithm. European Journal of Operational Research1 (1977). · Zbl 0374.90050
[9] Martello, S., Toth, P.: The 0–1 Knapsack problem, in: Combinatorial optimization (Christofides, N., Mingozzi, A., Sandi, C., Toth, P., eds.). London: J. Wiley 1979. · Zbl 0409.90063
[10] Morin, T. L., Marsten, R. E.: Branch and bound strategies for dynamic programming. Operations Research24 (1976). · Zbl 0352.90075
[11] Nauss, R. M.: An efficient algorithm for the 0–1 Knapsack problem. Management Science23 (1976). · Zbl 0337.90042
[12] Toth, P.: A new reduction algorithm for 0–1 Knapsack problems. Presented at ORSA/TIMS Joint National Meeting, Miami (November 1976).
[13] Zoltners, A. A.: A direct descent binary Knapsack algorithm. J. ACM25 (1978). · Zbl 0372.68012
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.