조합 문제로 고생했습니다.

Question

내 프로그램에 문제가 있습니다. 데이터 집합을 추출한 후 특정 숫자에 대한 조합이 있는지 테스트하고 싶습니다. 예를 들어, int 배열이 1 2 3 4 5 인 경우 7 조합이 있는지 알고 싶습니다. 3 + 4가 예라고 대답해야합니다.

나는 조합 수식을 사용해야합니다. 그래서 바깥 고리는 5C1..5C2..5C3..etc처럼 갈 수 있다고 생각했습니다. 가능한 한 모든 조합을 찾기 위해 한 번에 "take 1"을 한 다음 "take 2"를 시작했습니다. 문제는 실제 코드에서이를 구현하는 방법에 집착하고 있다는 것입니다.

저는 수학에별로 좋지 않습니다. 정의 된 루프 구조가 도움이 될 것입니다.

미리 감사드립니다.

Answer 1

여기 정수리스트의 모든 가능한 합계를 얻는 방법이다

public static void getAllPermutations(final List<Integer> data, 
    final Set<Integer> holder){ 

    if(data.isEmpty()){ 
     return; 
    } 
    final Integer first = data.get(0); 
    if(data.size() > 1){ 
     getAllPermutations(data.subList(1, data.size()), holder); 
     for(final Integer item : new ArrayList<Integer>(holder)){ 
      holder.add(first.intValue() + item.intValue()); 
     } 
    } 
    holder.add(first); 
} 

용도 :

List<Integer> data = Arrays.asList(1, 2, 3, 4, 5, 6); 
Set<Integer> permutations = new TreeSet<Integer>(); 
getAllPermutations(data, permutations); 
System.out.println(permutations); 

출력 :

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 이 솔루션은 당신에게 합계로 이어질 피연산자를 제공하지 않지만]

은

---

, 그것은 간단한 의사 다항식 시간 동적 프로그래밍이 문제에 대한이 1 + 2 + 3 + 4 + 5 + 6

Answer 2

신속하고 더러운 해결책은 인덱스 (두 차원 모두에서)가 배열에있는 숫자의 위치이고 값이 조합 인 2D 배열을 만드는 것일 수 있습니다. 이런 식으로 뭔가 : 당신은 지금 6 조합을 찾으려면

//int i[] = { 1, 3, 5}, operation is 'add' 
//you have a 3x3 array here: 
//\ |1 3 5 <- the original values at their corresponding indices for quick reference, the array is the bottom right 3x3 matrix 
//--+------ 
//1 |2 4 6  
//3 |4 6 8 
//5 |6 8 10 

int[][] a = new int[3][3]; 
//in a loop fill the array 

, 당신이 예에서 (6 동등한 값 x 및 y 인덱스를 모든 값을 확인하고 얻을 수 : 0/2 , 1/1 및 2/0). 그런 다음 원래 배열의 해당 색인에서 숫자를 찾습니다 (예 : 0/2 -> 1 및 5, 1/1 -> 3 및 3,2/0 -> 5 및 1).

이것은 (특히 더 큰 배열의 경우) 신속하고 매우 불완전한 방법이며 원하는 것보다 많은 순열을 반환 할 수 있습니다 (0,2 및 2/0은 조작 add과 동일 함). 그러나 이는 가능한 많은 작업 (예 : x = 1, y = 5 (결과 : 1) 및 x = 5, y = 1 (결과 : 5)에 대해 x ^y이 다를 수 있습니다.

Answer 3

-1에서 아무것도 포함됩니다 먼저 부자가 될 수 있다고 결정 22 두 가지 옵션이 있습니다. 배열 항목 중 하나를 사용하거나 이전에 설립 된 1을 사용하여 새 요소를 추가하십시오. 요청한 숫자만큼 부채꼴로 2 차원 테이블을 완성 할 수 있습니다.

bool findNode(int[] C , int givenNumber) { 
// compute the total sum 
int n = C.Length; 
int N = 0; 
for(int i = 0; i < n; i++) N += C[i]; 
// initialize the table 
T[0] = true; 
for(int i = 1; i <= N; i++) T[i] = false; 
// process the numbers one by one 
for(int i = 0; i < n; i++) 
    for(int j = N - C[i]; j >= 0; j--) 
    if(T[j]) T[j + C[i]] = true; 

return T[givenNumber]; 
} 

이것은 O (n * 합)입니다. 사실 O(n*given_number)으로 확인하는 것으로 충분합니다.