배열의 벡터에서 수 k와 같은 원소의 합을 가진 배열을 만듭니다.

Question

정수 배열이 n 인 벡터 (배열이라고 부름)와 숫자 k가 있습니다. 벡터를 만드는 방법을 찾아 내야 만합니다. Sol의 모든 원소의 합이 k이고 Sol [i]가 Arrays [i]의 속성을 가지고 있다고합시다. 예 :

첫 번째는 n이고, 두 번째는 k이며, 그 다음 배열입니다.

입력 :

3 10 
1 2 3 
2 5 7 
4 6 8 

콘솔 : 나는 단순히 되돌아 사용할 수 있지만, 거대한 복잡성이

2 2 6 

.

3 10 
1 2 3 
2 5 7 
4 6 8 

ex for: 
8 < 10, viable solution 
6 < 10, viable solution 
4 < 10, viable solution 

7 + 8 = 15 < 10 false never check this path again 
7 + 6 = 13 < 10 false never check this path again 
... 

내가 이렇게해도 큰 복잡성에 대한 몇 가지 상황이 있습니다 : 나는 바닥에서 시작하여 각 포인트에 대한이 같은 가능한 솔루션의 목록을 아래에서 포인트를 결합하는 알고리즘을 만들기 위해 노력했다. 저는 O (m * k) 복잡성을 목표로합니다. 여기서 m은 모든 입력 배열 길이의 합입니다.

import java.io.File; 
import java.io.FileNotFoundException; 
import java.util.Iterator; 
import java.util.Scanner; 
import java.util.Vector; 

public class Main { 
    static Vector<Vector<Integer>> Arrays; 
    static int Arrays_lenght; 
    static int sum; 

    public static void main(String[] args) throws FileNotFoundException 
    { 
     Scanner data_in = new Scanner(new File("data.in")); 
     Arrays_lenght = data_in.nextInt(); 
     sum = data_in.nextInt(); 

     Arrays = new Vector<>(); 
     data_in.nextLine(); 

     //read vectors 
     for(int i = 0; i < numar_vectori; i++) 
     { 
      String temp = data_in.nextLine(); 
      Scanner _temp = new Scanner(temp); 
      Vector<Integer> temp_vector = new Vector<>(); 
      while (_temp.hasNext()) { 
       temp_vector.add(_temp.nextInt()); 
      } 
      Arrays.add(temp_vector); 
     } 

     Iterator<Vector<Integer>> itr = Arrays.iterator(); 
     while (itr.hasNext()) 
      System.out.printf("%s\n", itr.next().toString()); 
    } 
} 

여기 내 코드가 java의 입력 파일을 읽지 않습니다. Sol 벡터를 O (m * k) 복잡도로 만들려면 어떻게해야합니까? 여기서 m은 모든 입력 배열 길이의 합입니까?

Answer 1

동적 프로그래밍 용액 (I 입력 어레이 A[][] 자연수 포함되어 있다고 가정)

2 차원 배열을 B[][] 생성 -, K + 1 열 N 라인 제로 채우기.

for every element of the first input array el=A[0][ix] 
    set B[0][el] = ix+1 
    // incrementing is useful to separate filled entries from empty ones 

for i = 1 to n-1 
    for every element of i-th input array `el=A[i][ix]`: 
     for every ik index in range 0..Sum-el 
      if B[i - 1, ik] is filled then 
       set B[i, ik + el] = ix+1 

at the end: 
if B[N-1, K] is filled 
    unwind indexes of elements that produce needed sum 

번째 스테이지 (첫번째 행의 배열을 제외하고), 입력 행렬의 각 요소에 대한 K 개까지의 시간을 실행하므로 시간 복잡도는 (K *에서의 M) O이다.