알고리즘 - 합계가 주어진 범위에있는 부분 집합 수 찾기

이것은 인터뷰 질문입니다. 나는 일련의 수 (중복, 가능한 음수)와 범위의 상한 및 하한을 부여 받았다. 범위 내에서 가능한 한 많은 수의 하위 집합을 찾아야합니다. 저는 특정 금액 (find all subsets that sum to a particular value)을 찾는 질문을 보았습니다.하지만 범위 내 모든 숫자에 대해 그렇게하려고하지 않는 것이 가장 효율적인 방법입니다.알고리즘 - 합계가 주어진 범위에있는 부분 집합 수 찾기

범위는 -10^7 ~ 10^7 일 수 있습니다.

출처

2016-12-27 Bharg

링크 된 답변이 채택 된 것처럼 보입니다. 아마 이미 생각해봤을 지 모르지만 질문에 갇혀있는 부분을 설명하지는 않으므로 단지 솔루션을 작성하는 것 이외의 유용한 도움을 제공하기가 어렵습니다. –

분명히 NP 하드입니다. 동적 프로그래밍 방식은 자연 스럽다. –

이 문제는 적어도 부분 합계 문제만큼 어렵지 만 가중치의 합계가 제한되어있을 때 np-hard로 남아 있거나 다루기 쉽게되는지 여부는 알 수 없습니다. –

기존의 DP for subset sum은이 문제를 해결하기 위해 수정할 수 있습니다. 주어진 합계의 솔루션이 존재하는지 여부를 나타내는 부울 표시기 대신 개수를 유지합니다.

def subset_sum_count(lst, a, b): 
    sum_count = collections.Counter({0: 1}) 
    for x in lst: 
     for s, c in list(sum_count.items()): 
      sum_count[s + x] += c 
    return sum(c for (s, c) in sum_counts.items() if a <= s <= b)

출처

2016-12-27 18:27:07

알고리즘 - 합계가 주어진 범위에있는 부분 집합 수 찾기

답변

관련 문제