위키 디피아에서 Subset sum problem 이라는 항목을 보다가
오호 이런 것도있구나 하면서 가방 문제도 접해보고 한번 슈도코드라도 짜 보자! 하고 있었습니다.
그런데 어제 오늘로 죙일 펜만 굴리고 구겨서 쓰레기통에 던진 A4만 몇장인지 모르겠네요... 흑흑
물론 스택오버플로우에서도, 구글링에서도 자료를 많이 찾아봤지만 정확한! 해답이 아직 안보이네요.
2가지 예제만 들어드리겠습니다.
A = {1,2,3,4,5,6,7,8} K = 9 일때
[1,8], [2,7], [3,6], [4,5] 4개가 가장 이상적이다.
그래서 [1,2,3], [4,5], [6], [7], [8]은 수의 낭비다 라고 정의하더군요
왜냐하면 Pipe ReArrange라고 말하긴하는데 아직 정확한 정의는 없습니다.
파이프 공장에서 파이프를 자르는데, 최소한의 짜투리만 남기고 잘라야 하는 법칙을 따르는 것이지요.
그렇지만 아래 예제처럼은 당연히 이래야만 합니다.
A = {19,23,41,5,40,36} K = 44 일때
[19,23], [41], [5,36], [40] 가 나오는게 당연하다.
Java를 이용하면서 서브셋을 짜 봤는데 첫번째 예제처럼 [1,2,3] 식으로 돌아가게 뿐 못하겠네요..
참조할 만한 자료를 얻어갈 수 있었으면 하는 바램입니다 여러분! :)
외부펌금지
글쓰기