joyyir   1년 전

안녕하세요 컴퓨터공학을 전공하고있는 학생입니다.

다름이 아니라, 알고리즘 수업에서 동적계획법 과제를 해결하는데 제 능력으로 도저히 해결이 안되어 도움을 청하고자 합니다.

문제는 이렇습니다.

어떤 공장에서 서로 다른 n개의 부품이 조림해서 제품을 만든다고 하자. 이 때, 부품을 조립하는 순서에 따라서 비용이 다르다고 하자.
즉, 부품 A-B-C로 조립하는 비용과 B-C-A로 조립하는 비용이 다르다. 가장 최소 비용으로 부품들을 조립하는 방법을 찾는 알고리즘을 작성하라. 단. 한번에 부품 하나씩만 붙일 수 있다. 즉, 조립된 부품들의 집합들을 하나로 조립할 수는 없다.

몇 시간동안 고민을 했는데도 최적의 원칙을 만족하는 부분을 찾을 수 없었습니다. 그래서 재귀 관계식을 세울 수가 없었습니다.

답 전체가 아니라도 힌트가 되는 부분이라도 알려주시면 감사하겠습니다.

hahaha   1년 전

부품의 개수(n)가 몇개인가요?

n이 작은 경우라면, bitmask를 이용한 dp로 풀 수 있습니다.

dp[i]에서 i를 비트(2진수)로 생각했을 때, 비트가 1인경우 조립된 경우, 비트가 0인 경우 아직 조립하지 않은 경우로 생각하시면 됩니다.

예를 들어서 i가 14라면, 1110(2)입니다. 2^j의 j가 부품의 번호라 생각했을 때, 1110(2)는 부품 2,3,4(편의상 1부터 생각했습니다.)이 조립된 상태입니다.

1110의 상태를 만드려면 1100(2)에서 2를 조립하거나, 1010(2)에서 3일 조립하거나, 110(2)에서 4를 조립하는 경우 중 최소 비용을 가지는 경우일 겁니다.


비트 다이나믹 관련하여 찾아보시면, 참고하실 좋은 자료들 많을거에요.ㅎㅎ


하지만 이 방법은 메모리 및 시간의 제한 때문에, n이 보통 20내외 일경우만 위 방법을 사용합니다


댓글을 작성하려면 로그인해야 합니다.