earticle

영어

This paper proposed a division algorithm of performance complexity O(n(n+1)/2) for a change-making problem(CMP) in which polynomial time algorithms are not known as NP-hard problem. CMP seeks to minimize the sum of the xj number of coins exchanged when a given amount of money C is exchanged for cj, j = 1,2 ⋯ , n coins. Known polynomial algorithms for CMPs are greedy algorithms(GA), divide-and-conquer (DC), and dynamic programming(DP). The optimal solution can be obtained by DP of O(nC), and in general, when given C>2n , the performance complexity tends to increase exponentially, so it cannot be called a polynomial algorithm. This paper proposes a simple algorithm that calculates quotient by dividing upper triangular matrices and main diagonal for k × n matrices in which only j columns are placed in descending order of cj of n for cj ≤ C and i rows are placed k excluding all the dividers in cj. The application of the proposed algorithm to 39 benchmarking experimental data of various types showed that the optimal solution could be obtained quickly and accurately with only a calculator.

한국어

본 논문은 NP-난제로 다항시간 알고리즘이 알려져 있지 않은 거스름돈 만들기 문제(CMP)에 대해 O(n(n+1)/2) 수행 복잡도의 나눗셈 알고리즘을 제안하였다. CMP는 주어진 돈 O를 cj, j = 1,2 ⋯ , n의 동전으로 교환할 경우 교환되는 동전 개수 xj의 합을 최소화 시키는 문제이다. CMP에 대해 알려진 다항시간 알고리즘으로는 욕심쟁이 알고리즘(GA), 분할정복(DC)과 동적 계획법(DP)이 있으나 최적 해는 O(nC)의 DP로 구할 수 있으며, 일반적으로 C>2n 으로 주어진 경우 수행 복잡도는 지수적으로 증가하는 경향이 있어 다항시간 알고리즘이라고 할 수 없다. 본 논문에서는 cj ≤ O에 한해, j 열에 n개의 cj 내림차순으로 배치하고, i 행에는 cj의 약수를 모두 제외시킨 k개의 동전을 배치한 k × n 행렬에 대해 상삼각행렬과 주대각선 셀에 대해 나눗셈을 하여 몫(quotient)을 구하는 단순한 알고리즘을 제안한다. 제안된 알고 리즘을 다양한 유형의 39개 벤치마킹 실험 데이터에 적용한 결과 최적 해를 단순히 계산기만을 사용하여도 빠르고 정확 하게 구할 수 있음을 보였다.