Application of 0/1- knapsack problem in optimal decision making

Sushil Chandra Dimri; Bhawnesh Kumar; Kamlesh Chandra Purohit; Mangey Ram

Sushil Chandra Dimri Graphic Era deemed to be University, Dehradun, Uttarakhand, India.
Bhawnesh Kumar Graphic Era deemed to be University, Dehradun, Uttarakhand, India
Kamlesh Chandra Purohit Graphic Era deemed to be University, Dehradun, Uttarakhand, India.
Mangey Ram Graphic Era deemed to be University, Dehradun, Uttarakhand,; Institute of Advanced Manufacturing Technologies, \\ Peter the Great St. Petersburg Polytechnic University, 195251 Saint Petersburg, Russia.

Abstract

Dynamic programming approach was designed in year 1950’s by mathematician Richard Bellman. Dynamic programming approach works in bottom up fashion, it first divide the problem in small overlapped sub problems and then solve them starting from the smallest one and store the solution in a table. The main idea of dynamic programming is a recurrence relation which relates the solution of previous sub problems with the current instance of the problem. Step wise it increases the size of the problem and finally reached to original initial problem. 0/1 knapsack is one of the popular problem solved by using dynamic programming approach, this problem can be used to solve many problem like optimum job scheduling, strategy selection, resource allocation, policy making and many more. This paper presents one of such application of 0/1 knapsack problem in best strategies selection to optimize the objective achievements.