• home
• current students
• graduate
• events

Presenter: Feifan Xing
Supervisor:

Date: Wed, August 3, 2022
Time: 09:00:00 - 10:00:00
Place: via Zoom - please see link below

ABSTRACT

Zoom link: https://uvic.zoom.us/j/86468724274?pwd=VktOLzlaeTQ2eEQzZzMxSG05aVI5Zz09

Meeting ID: 864 6872 4274

Password: 367370

Abstract: The 0-1 knapsack problem is a classic non-deterministic polynomial complete problem and has a wide range of applications in many fields. It is a multistage decision problem and can be solved using the dynamic programming algorithm. First, this report presents the concept, terminology, conditions, and steps of dynamic programming algorithms. Then, two algorithms are introduced to solve the 0-1 knapsack problem, namely Tradition Dynamic Programming (TDP) and Efficient Dynamic Programming (EDP). It is shown that the time complexity and space complexity of TDP are both O(nW), and the time complexity of EDP is O(nW) while the space complexity is only O(W). However, EDP cannot obtain any information about item selection, which limits its application. Next, a new hybrid algorithm that combines EDP and the divide-and-conquer method is proposed. This algorithm eliminates the backtracking process used in TDP for item selection but can still determine which items are in the optimal solution. Analysis shows that the time complexity of the hybrid algorithm is O(nW) and the space complexity is O(W+logn). Results are presented which show that compared with TDP, the new hybrid algorithm has significant advantages in solving large-scale knapsack problems.