초록

용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

The subset-sum problem is to find out whether or not the element sum of a subset within a finite set of numbers is equal to a given value. The problem is a well-known NP-complete problem, which is difficult to solve within a polynomial time. Genetic algorithm is a method for finding the optimal solu...

The subset-sum problem is to find out whether or not the element sum of a subset within a finite set of numbers is equal to a given value. The problem is a well-known NP-complete problem, which is difficult to solve within a polynomial time. Genetic algorithm is a method for finding the optimal solution of a given problem through operations such as selection, crossover, and mutation. Dynamic programming is a method of solving a given problem from one or several subproblems. In this paper, we design and implement a genetic algorithm that solves the subset-sum problem, and experimentally compared the time performance to find the answer with the case of dynamic programming method. We selected a total of 17 test cases considering the difficulty in a set with 63 elements of positive number, and compared the performance of the two algorithms. The presented genetic algorithms showed time performance improved by 84% on 13 of 17 problems when compared with dynamic programming.

Keyword