nayuta9010   1년 전

1182번 부분집합1같은 경우에는 모든 경로를 검색하는 방법을 선택해서 했습니다.

1208번 같은 경우에는 전체검색을 해야 될 경우 최대 O(2^n) 여서 불가능 했습니다.

백트래킹을 사용해서 유망함수를 잘 짜면 될 것 같은데 여기서 부분집합의 합을 구할때

음수가 포함되어 있어도 유망함수의 구현정도에 따라서 문제 클리어가 가능할까요?

여러모로 짜보고 있는데 답이 나오지 않아서 가능 여부라도 알고 싶습니다.


WeissBlume   1년 전

이 문제의 경우에는 n이 작기때문에 반으로 쪼개는 2^(n/2) 방식을 사용하거나,
수의 범위가 제한적이므로 동적계획법을 이용해서 해결하는 것이 가장 쉬운 방법입니다.

nayuta9010   1년 전

그럼 음수가 포함되어있는 부분집합의 합 문제를 풀때 백트래킹은 불가능한 접근방법일까요?

문제 풀이와는 별도로 가능 여부가 궁금합니다.

WeissBlume   1년 전

'효율적인' 백트래킹은 잘 모르겠네요 :$ 당장 생각나는 유망함수로는 서브트리-남은 수들-로 생성가능한 합의 최소와 최대를 찾아서 그 사이에 필요한 값이 들어가는지 뿐이라서요.

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