숫자에 가장 잘 맞는 방법

다음과 같은 정수가 {2,9,4,1,8}입니다. 이 집합을 두 개의 하위 집합으로 나눠서 집합의 합이 각각 14와 10이되도록해야합니다. 내 예제에서는 대답은 {2,4,8}과 {9,1}입니다. 나는 어떤 코드도 찾고 있지 않다. 나는이 문제를 해결하기위한 표준 알고리즘이 있어야한다고 확신한다. 인터넷 검색에 성공하지 못해서 혼자만 찾았 기 때문에 여기에 내 질문을 올렸습니다. 그렇다면이 문제에 접근하는 가장 좋은 방법은 무엇일까요?숫자에 가장 잘 맞는 방법

내 시도는 내가이 방법을 알고

public class Test { 
    public static void main(String[] args) { 
     int[] input = {2, 9, 4, 1, 8}; 
     int target = 14; 
     Stack<Integer> stack = new Stack<>(); 
     for (int i = 0; i < input.length; i++) { 
      stack.add(input[i]); 
      for (int j = i+1;j<input.length;j++) { 

       int sum = sumInStack(stack); 

       if (sum < target) { 
        stack.add(input[j]); 
        continue; 
       } 

       if (target == sum) { 
        System.out.println("Eureka"); 
       } 

       stack.remove(input[i]); 
      } 

     } 
    } 

    private static int sumInStack(Stack<Integer> stack) { 
     int sum = 0; 
     for (Integer integer : stack) { 
      sum+=integer; 
     } 
     return sum; 
    } 
}

이

출처

2016-12-25 Tiny Rick

여러 배낭 문제입니다. https://en.wikipedia.org/wiki/Knapsack_problem 또는 빈 포장 문제. 모든 요소를 사용해야하는지 여부와 같은 지정하지 않은 추가 제약 조건에 따라 약간 다릅니다. –

@ErwinBolwidt 모든 요소는 끝에 사용해야합니다. 내 질문에 2 가지 하위 집합 결과가 있다고 명시했습니다. 부모 집합을 n 개의 하위 집합으로 나눌 수있는 일반 알고리즘이 필요합니다. 여기서 각 하위 집합은 지정된 개수까지만 합산됩니다. –

내가 두 부분 집합으로이 세트를 분할해야하는 문제를 해결하기 위해 근처에도없는 ...이 같았다 합 있도록 세트의 결과는 각각 14와 10이됩니다.

하위 집합이 특정 값의 합계 인 경우 전체 집합의 합계가 해당 값의 합계 (예 : 14 + 10 = 24)가되어야합니다. 두 부분 집합 만 찾으면 문제는 그리 어렵지 않습니다. 그 값 중 하나와 합한 부분 집합을 찾아 나머지 집합의 요소는 다른 값과 합쳐 져야합니다. 예를 들어

하면, {2,9,4,1,8}을 준 설정, 당신은 대답은 {9,1}, {2,4,8}이지만, 그 유일한 답이 아니다 것을 알 수 했다; {2,8}, {9,4,1}도 있습니다.

출처

2016-12-25 05:43:00 Caleb

"매우 어렵지 않다"라는 관점에서? 순진한 방법으로 구현하는 방법, 또는 문제의 시간 복잡성? :-) –

@ 캐롤 그래, 네. 가장 좋은 해결책은 모든 가능한 세트를 나열하는 것입니다. 지적 해 주셔서 고맙습니다. –

답변

관련 문제