earticle

영어

A dynamic planning(DP) method of is well-known for a change-making problem(CMP) in which the NP-hard, the polynomial time algorithm is not known. Recently, a division algorithm(DA) has been proposed, which dramatically reduces  × of the dynamic planning method to n × n. This paper proposes an algorithm that extremely reduces the n × n of DA to 1 × n or 2 × n. The proposed method excludes a divider in Ci = cj, j - 1,2,⋯,n and determines the winner accordingly if there is a divider given total cost W or in unique value in ci . If |ci| ≥ 2, the final winner is determined by performing a bilateral match with the maximum of odd and even numbers, two maximums of odd numbers, or two maximums of even numbers. As a result of applying the proposed algorithm to 39 experimental data, 69.23% of cases were determined as a single winner and 28.20% of cases of bilateral match, showing an algorithm that dramatically shortened execution time.

한국어

NP-난제로 다항시간 알고리즘이 알려져 있지 않은 거스름돈 만들기 문제(CMP)에 대해 n × W의 동적계획법이 널리 알려져 있다. 최근 들어 동적계획법의 n × W을 n × n으로 획기적으로 축소시킨 나눗셈 알고리즘(DA)이 제안되었 다. 본 논문은 DA의 n × n을 1 × n 또는 2 × n으로 극도로 축소시킨 알고리즘을 제안한다. 제안 방법은 Ci = cj, j - 1,2,⋯,n에 대해 약수를 제외시키고 ci 에 유일 값 또는 주어진 총액 W의 약수가 존재하면 해당 ci 로 승자를 결정한다. 만약 |ci| ≥ 2이면 홀수와 짝수의 최대치, 홀수의 최대치 2개, 또는 짝수의 최대치 2개로 양자대결을 수행하여 최종 승자를 결정한다. 제안된 알고리즘을 39개의 실험 데이터에 적용한 결과 단일 승자로 결정된 경우가 69.23%, 양자 대결을 한 경우가 28.20%에 불과하여, 수행시간을 획기적으로 단축시킨 알고리즘임을 보였다.