henongj   3년 전


프로그램은 , 집어넣을 수 있는 짐을 모든 경우의 수 대로 집어넣어서 maximum을 구하는 것을 목적으로 합니다.

1 - pick_thing 이라는 함수를 재귀호출합니다.

2 - 함수는 picker 부터 n번째 짐에 대해 반복문(i)을 실행합니다.

    3_ - pick_thing에서 p[i]번째 짐을 집어넣을 수 있는지?

    3.true - 그것을 메모에 기입하고 다음 짐을 지목한 뒤 pick_thing을 호출합니다.

    3.false - 다음 짐을 지목합니다.



4. main 함수에서 memo [ weight ] 의 값중 최대값을 구해서 출력합니다.

대략 이런 구조의 프로그램입니다.

하지만 memo에 적은 값을 pick_thing이 재귀호출하면서 고르지 않은 값까지 가져다 써서 훨씬 큰 값이 나오는 문제가 나옵니다.

제가 재귀함수에 대한 지식이 너무 짧은지 접근법이 잘못된 것 같습니다.

memo에서 가져다 쓰는 부분을 새로 지역변수로 선언해서 대체해봐도 안 되고

bool flag 배열을 새로 선언해서 고른 것의 flag를 false로 바꾸자니 코드가 커져서 방식 자체가 틀려먹었는데 계속 땜질을 하는 기분이 듭니다.

어떤 부분을 고쳐야 할지, 어떤 생각이 잘못됐는지 이 미천한 군바리에게 고견을 주시면 참으로 감사하겠습니다.

넣은 입력은 여기저기에서 반례를 찾아봐서 가져다 썼습니다.

6 9

3 6

2 7

4 6

4 2

4 10

1 5

출력 값

output : 26

실제 답 : (3,6)+(2,7)+(4,10) : 23입니다.



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