The 0-1 knapsack problem is one of the classical NP-hard problems and has been one of the hot research topics in the last few decades. It offers many practical applications in optimization and applied mathematics, such as project selection, resource distribution, investment decision-making and so on. Simultaneity in previous studies DNA molecular computation usually be used to solve NP-complete continuous path search problems (for example HPP, traveling salesman problem), rarely for NP problems with discrete solutions result, such as the 0-1 knapsack problem, graph coloring problem. In this paper, we present a new algorithm for solving the 0-1 knapsack problem with DNA molecular operations. For 0-1 knapsack problem with n distinct items, weight capacity C and total profits W, we reasonably design fixed length DNA strands representing items, take appropriate steps and get the solutions of the problem in proper length range using O(n + C + W) time. We extend the application of DNA molecular operations and simultaneity simplify the complexity of the computation.
GareyM.R. and JohnsonD.S., Computers and Intractability: A Guide to the Theory of NP-completeness. W.H. Freeman and Company, 1979.
2.
AdlemanL.M., Molecular computation of solution to combinatorial problems, Science266 (1994), 1021–1024.
3.
LiptonR.J., DNA solution of HARD computational problems, Science268 (1995), 542–545.
4.
RoweisS., WinfreeE., BurgoyneR., ChelyapovN.V., GoodmanM.F., RothemundP.W.K. and AdlemanL.M., A sticker based model for DNA computation, Journal of Computational Biology5 (1998), 615–629.
5.
OuyangQ., KaplanP.D., LiuS. and LibchaberA., DNA solution of the maximal clique problem, Science278 (1997), 446–449.
6.
WinfreeE., LiuF., WenzlerL.A. and SeemanN.C., Design and self-assembly of two dimensional DNA crystals, Nature394 (1998), 539–544.
7.
SakamotoK., GouzuH., KomiyaK., KigaD., YokoyamaS., YokomoriT. and HagiyaM., Molecular computation by DNA hairpin formation, Science288 (2000), 1223–1226.
8.
SmithL.M., CornR.M., CondonA.E., LagallyM.G., FrutosA.G., LiuQ. and ThielA.J., A surface-based approach to DNA computation, Journal of Computational Biology5 (1998), 255–267.
9.
LiW.X., XiaoD.M. and HeL., DNA ternary addition, Applies Mathematics and Computation182 (2006), 977–986.
10.
XiaoD.M., LiW.X., YuJ., ZhangX.D., ZhangZ.Z. and HeL., Procedures for a dynamical system on {0,1}n with DNA molecules, BioSystems84 (2006), 207–216.
11.
WangX.L., BaoZ.M., HuJ.J., WangS. and ZhanA., Soling the SAT problem using a DNA computing algorithm based on ligase chain reaction, BioSystems91 (2008), 117–125.
12.
LeeJ.Y., ShinS.Y., ParkT.H. and ZhangB.T., Solving traveling salesman problems with DNA molecules encoding numerical values, BioSystems78 (2004), 39–47.
13.
NarayananA., ZorbalasS., et al., DNA algorithms for computing shortest paths, in: KozaJ.R. (Ed.), Proceedings of the Genetic Programming, 1998, pp. 718–723.
14.
ChangW.L., LinK.W., ChenJ.C., et al., Molecular solutions of the RSA public-key cryptosystem on a DNA-based computer, Journal of Supercomputing61 (2012), 642–672.
15.
ChangW.L., RenT.T., LuoJ., et al., Quantum algorithms for biomolecular solutions of the satisfiability problem on a quantum machine, IEEE Transactions on Nanobioscience7 (2008), 215–222.
16.
ChangW.L., Fast parallel DNA-based algorithms for molecular computation: The set-partition problem, IEEE Transactions on Nanobioscience6 (2007), 346–353.
17.
WangZ., HuangD., TanJ., et al., A parallel algorithm for solving the n-queens problem based on inspired computational model[J], Biosystems131 (2015), 22–29.
18.
LiuX.C., YangX.F., LiS.L. and DingY., Solving the minimum bisection problem using a biologically inspired computational model, Theoretical Computer Science411 (2010), 888–896.
19.
WangZ.C., ZhangY.M., ZhouW.H. and LiuH.F., Solving traveling salesman problem in the Adleman-Lipton model, Applied Mathematics and Computation219 (2012), 2267–2270.
20.
Castellanos-GarznJ.A., GarcaC.A., NovaisP., et al., A visual analytics framework for cluster analysis of DNA microarray data[J], Expert Systems with Applications40(2) (2013), 758–774.
21.
GareyM.R. and JohnsonD.S., Computers and Intractability: A Guide to the Theory of NP-completeness, W. H. Freeman and Company, 1979.
22.
ZimmermannK.H., IgnatovaZ. and IsraelM.P., DNA Computing Models, Springer-Verlag, 2008, pp. 146–147.
23.
WangZ., TanJ., HuangD., et al., A biological algorithm to solve the assignment problem based on DNA molecules computation, Applied Mathematics and Computation244 (2014), 183–190.
24.
YamamuraM., HirotoY. and MatobaT., Solutions of shortest path problems by concentration control, Lect Notes Comput Sci2340 (2002), 231–240.
25.
ZhangY., ChuC.H., ChenY., et al., Splice site prediction using support vector machines with a Bayes kernel, Expert Systems with Applications30(1) (2006), 73–81.
26.
BraichR.S., JohnsonC., RothemundP.W.K., HwangD., ChelyapovN. and AdlemanL.M., Solution of a satisfiability problem on a gel-based DNA computer, in: Proceedings of the Sixth International Conference on DNA Computation (DNA 2000), Lecture Notes in Computer Science 2054, 2001, pp. 27–42.
27.
ZhangH.Y. and LiuX.Y., A CLIQUE algorithm using DNA computing techniques based on closed-circle DNA sequences, Biosystems105 (2011), 73–82.
28.
DarehmirakiM., A new solution for maximal clique problem based sticker model, Biosystems95 (2009), 145–149.
29.
BraichR.S., JohnsonC., RothemundP.W.K., ChelyapovN. and AdlemanL.M., Solution of a 20-variable 3-SAT problem on a DNA computer, Science296 (2002), 499–502.
30.
WangZ., HuangD., MengH., et al., A new fast algorithm for solving the minimum spanning tree problem based on DNA molecules computation, Biosystems114(1) (2013), 1–7.
31.
TingC.J., WuK.C. and ChouH., Particle swarm optimization algorithm for the berth allocation problem, Expert Systems with Applications41(4) (2014), 1543–1550.
32.
ChangW.-L. and VasilakosA.V., Molecular algorithms of implementing bio-molecular databases on a biological computer, IEEE Transactions on Nanobioscience14(1) (2015), 104–111.
33.
ChangW.-L., RenT.-T. and FengM., Quantum algorithms and mathematical formulations of bio-molecular solutions of the vertex cover problem in the finite-dimensional hilbert space, IEEE Transactions on Nanobioscience14(1) (2015), 121–128.
34.
ChangW.-L. and VasilakosA.V., Molecular Computing: Towards a Novel Computing Architecture for Complex Problem Solving (Studies in Big Data), Springer, ISBN-13:978-3319051215, ISBN-10:3319051210, 2014.
35.
XiaoD., LiW., ZhangZ., et al., Solving maximum cut problems in the Adleman– Lipton model, Biosystems82(3) (2005), 203–207.
36.
PăunG., RozenbergG. and SalomaaA., DNA Computing, SpringerBerlin Heidelberg, 1998.
37.
ZouD., GaoL., LiS., et al., Solving 0-1 knapsack problem by a novel global harmony search algorithm, Applied Soft Computing11(2) (2011), 1556–1564.
38.
CaptivoM.E., ClímacoJ., FigueiraJ., et al., Solving bicriteria 0-1 knapsack problems using a labeling algorithm, Computers & Operations Research30(12) (2003), 1865–1886.
39.
ZhangX., HuangS., HuY., et al., Solving 0-1 knapsack problems based on amoeboid organism algorithm, Applied Mathematics and Computation219(19) (2013), 9959–9970.
40.
AzadM.A.K., RochaA.M.A.C. and FernandesE.M.G.P., Improved binary artificial fish swarm algorithm for the 0-1 multidimensional knapsack problems, Swarm and Evolutionary Computation14 (2014), 66–75.
41.
GuoM., ChangW.L., HoM., et al., Is optimal solution of every NP-complete or NP-hard problem determined from its characteristic for DNA-based computing, BioSystems80(1) (2005), 71–82.
42.
SanchesC.A.A. and SomaN.Y., A polynomial-time DNA computing solution for the Bin-Packing Problem, Applied Mathematics and Computation215(6) (2009), 2055–2062.
43.
WangZ., HuangD., MengH., et al., A new fast algorithm for solving the minimum spanning tree problem based on DNA molecules computation, Biosystems114(1) (2013), 1–7.
44.
HaoG., Gui-LuL. and FengL., Quantum algorithms for some well-known NP problems, Communications in Theoretical Physics37(4) (2002), 424.
45.
WangZ., PuJ., CaoL., et al., A parallel biological optimization algorithm to solve the unbalanced assignment problem based on DNA molecular computing, International Journal of Molecular Sciences16(10) (2015), 25338–25352.
46.
WangZ.C., HuangD.M., TanJ., et al., A parallel algorithm for solving the n-queens problem based on inspired computational model, BioSystems131 (2015), 22–29.
47.
ChangW.L., Fast parallel DNA-based algorithms for molecular computation: Quadratic congruence and factoring integers, IEEE Transactions on Nanobioscience11(1) (2012), 62–69.
48.
ChangW.L., GuoM. and HoS.H., Fast parallel molecular algorithms for DNA-based computation: Factoring integers, IEEE Transactions on Nanobioscience4(2) (2005), 149–163.
49.
JianF. and DandanS., Complex network theory and its application research on P2P networks, Applied Mathematics and Nonlinear Sciences1(1) (2016), 44–50.
50.
RosaM. and NúñezM.L.G., Multiplier method and exact solutions for a density dependent reaction-diffusion equation, Applied Mathematics and Nonlinear Sciences1(2) (2016), 311–320.
