부분 집합 합의 편차

Question

주어진 숫자 배열을 감안할 때 합계가 주어진 수의 배수 인 숫자 집합을 찾고 싶습니다.

나는 이것이 부분 집합 합의 변형이라고 알고 있습니다. 그러나 문제는 무한 수의 배수가 있다는 것입니다. 그래서 나는이 문제에 대한 역동적 인 문제 해결책을 생각할 수 없다.

그래서 서브 세트 합계 문제를 어떻게 확장합니까?

Answer 1

모든 (0이 아닌) 숫자에는 무한히 많은 배수가 있지만, 세트의 모든 요소의 합계보다 적은 수의 배수가 매우 한정적입니다. 즉, 집합의 요소 합계로 생성 될 수있는 최대 배수를 항상 상한값으로 설정할 수 있습니다. 이렇게하면 표준 pseudopolyomial-time DP 기법을 사용하여 문제를 해결할 수 있습니다.

희망이 도움이됩니다. 합계 서브 세트

Answer 2

의사 다항식 DP 용액 상태 DP 사용

DP(n, s) = Number of ways of getting a sum of s using first n elements of the set 

및 O (NS) 시간이 걸린다. d의 모든 배수를 찾고 싶다면 d와 나머지 부분 합계에만 관심이 있습니다. 모듈성은 분산적임을 기억하십시오. 따라서, I는 한 규칙이 실제 pseudopolynomial 용액에이어서 같은 O (ND)와 시간 O (ND)로 감소

DP(n, m) = Number of subsets whose sum = m mod d using the first n elements 

공간에 DP 상태 변경을 허용하는 단부로부터 DP 어레이를 통과 할 수있다 오직 O (s) 공간 만 사용하십시오. 그것은 여기서 할 수 없습니다. O (2m) 메모리를 사용하여 이전 및 현재 DP 어레이를 저장하는 것이 가장 좋습니다.

Answer 3

다음은 합계 값을 계산할 수있는 방법의 수를 찾는 코드입니다.

공공 정적 무효 메인 (문자열 []에 args) {

Scanner scan=new Scanner(System.in); 
    int n=scan.nextInt();//number of elements in the set 
    int m=scan.nextInt();//sum needs to be calculated 
    scan.nextLine(); 

    int[] setValue=new int[m]; 
    long[][] setSplit=new long[m+1][n+1]; 
    for(int i=0;i<m; i++) 
     { 
     setValue[i]=scan.nextInt(); 
    } 
    setSplit[0][0]=1; 
    //when sum is 0 
    for(int i=1; i<m+1; i++) 
     { 
     setSplit[i][0]=1; 
    } 
    //when sum is more than 0 but set element is 0 
    for(int j=1; j<n+1; j++) 
      { 
      setSplit[0][j]=0; 
     } 
    int temp=0; 
    for(int i=1; i<=m; i++) 
     { 

     for(int j=1; j<n+1; j++) 
      { 
      setSplit[i][j]=setSplit[i-1][j]; 
      if(j>=setValue[i-1]) 
       {  

       setSplit[i][j]=setSplit[i][j]+setSplit[i][j-setValue[i-1]]; 

      } 
     } 

    } 
    // System.out.println(Arrays.deepToString(setSplit)); 

    System.out.println(setSplit[m][n]);/*this will give number of ways sum can be calculated*/ 
}