세트의 어떤 숫자가 다른 주어진 숫자에 추가되는지 찾는 방법은 무엇입니까?

StackOverflow https://stackoverflow.com/questions/1202540

문제

여기에 회계 시스템을 사용하면서 겪는 문제가 있습니다.

일련의 거래가 있지만 그 합계가 회계 부서에서 생각하는 금액과 같지 않습니다.그들은 수학에 의문을 제기하는 것이 아니라 거래가 포함되는 것뿐입니다 :p

합계가 주어진 금액과 일치하도록 하기 위해 세트에서 어떤 거래를 포함하지 않아야 하는지 결정하는 데 도움이 되는 알고리즘이 있습니까?

Given Set:  
2  
4  
5  
7

Given Sum Amount:
13

Result Set:
2
4
7

편집하다:세트에 100개 미만의 거래가 있습니다.C# 예제가 없는 사람이 있나요? XKCD의 NP-완전 문제 해결 질문?

아, CS 학위를 받았어야 했는데.

도움이 되었습니까?

해결책

이것이 서브 세트 합계 문제입니다 NP- 완성. 그러나 이것이 하위 집합 합계를 찾는 알고리즘이 없다는 것을 의미하지는 않습니다.

다른 팁

이것이 배낭 문제 그리고 그것은 NP- 완성입니다. 작은 입력 세트를 제외하고는 정확히 쉽게 해결하지 못합니다. 괜찮은 크기의 문제 세트의 경우, 이는 일생 동안의 발표 문제 중 하나입니다.

즉, 유전자 변형 매듭 솔버가 있습니다.

위의 회원들이 말했듯이, 이것은 하위 세트 합계 문제 (또는 배낭 문제)입니다. 그러나 효율적으로 수행 할 수 없다고 말하는 것은 그리 정확하지 않습니다. 다항식 시간이 아니라 할 수 있습니다. 이 솔루션은 실제로 동적 프로그래밍 및 재귀 (및 의사 폴리 아동 시간)를 사용하여 매우 간단합니다.

정수가 주어지면 [a_1, ..., a_n]과 숫자 t,

A_1, ... a_i 사이에 요소의 서브 세트가 있는지 여부를 표시하려면 배열 [i, k]를 정의하십시오. (이것은 이진 행렬입니다).

그런 다음 재귀 관계를 다음과 같이 정의 할 수 있습니다.

s [i, k] = s [i-1, k] 또는 s [i-1, k-a_j

말로, 이것은 우리가 요소 a_i를 사용하거나 그렇지 않다는 것을 의미합니다. 답은 s [n, t]에 있습니다.

매트릭스를 구성하기위한 작업 부하는 무엇입니까? 글쎄, s에는 n*t 요소가 있습니다. 각 요소를 계산하려면 O (1) 작업을 수행해야합니다. 따라서 전체 실행 시간은 O (N*T)입니다.

이제이 시점에서 P = NP를 입증 한 것으로 보입니다. 이것은 다항식 시간 알고리즘 인 것 같습니다. 그러나 이진에서 입력 크기를 측정하므로 일부 p에 대해 t = 2^p를 측정합니다.

나는 위의 솔루션이 제대로 구현 될 때 비합리적이라고 말하지 않을 것이라고 생각합니다. 실제로, 많은 합리적인 문제 크기의 경우, 그것은 훌륭하게 수행 될 것입니다.

또한이 문제를 해결하기위한 휴리스틱이 있지만 해당 분야의 전문가는 아닙니다.

이것은 버전입니다 배낭 문제. NP가 완료되므로 좋은 일반적인 대답을 얻지 못할 것입니다. 거래 세트는 얼마나 큰가요? 당신이 보여준 것처럼 5인가 500과 비슷합니까?

좋아요.많은 사람들이 문제의 이름을 언급하고 NP가 얼마나 어려운지 언급했습니다.그리고 일반적으로 그들은 정확합니다.그러나 해결해야 할 매우 구체적인 사례가 있습니다.첫 번째 질문은 귀하의 100건의 거래가 올바른 거래에 가깝다고 생각하는지 여부입니다.당신은 약간의 총계("당신의" 총계)를 가지고 있습니다.그들은 약간의 합계를 가지고 있습니다.("실제" 합계).따라서 귀하의 거래 중 일부는 가짜입니다.거기에 몇 가지 가짜 거래만 있다고 의심된다면 이는 그리 나쁘지 않습니다.예를 들어 가짜 거래가 단 하나뿐인 경우를 생각해 보자.이 경우에는 100개의 다른 숫자만 확인하면 됩니다.2개의 가짜 거래가 있는 경우 100*99 수표를 보고 있으며 거의 ​​100,000,000단계를 거쳐 4개의 가짜 거래에서 상황이 이상해질 것입니다.하지만 당신이 하고 있는 일이 int를 추가하는 것뿐이라면 그다지 나쁘지는 않습니다.

또 다른 가능한 지름길은 데이터의 성격을 조사하는 것입니다(덧붙여서 100개의 "숫자"와 예상 합계를 게시하는 것이 가능합니까?).실제 금액에 비해 귀하의 금액이 얼마입니까?너무 큰 값을 제거하면 합계가 실제 합계보다 갑자기 낮아질 수 있습니까?그렇다면 해당 값은 가짜 값이 될 수 없다는 것을 알고 있습니다.예를 들어, 귀하의 예에서는 7이 반드시 필요합니다. 

        bool bBreak = false;
        int iEnd = 13;
        ArrayList ar1 = new ArrayList();
        ar1.Add(2);
        ar1.Add(4);
        ar1.Add(5);
        ar1.Add(7);

        String s1 = " ";
        foreach (int i in ar1)
        {
            if (i == iEnd)
            {
                s1 = "Result = " + i;
                bBreak = true;
            }
            if (bBreak) break;
            ArrayList ar2 = new ArrayList();
            ar2.AddRange(ar1);
            ar2.Remove(i);
            foreach (int j in ar2)
            {
                if ((i + j) == iEnd)
                {
                    s1 = "Results = " + i + ", " + j;
                    bBreak = true;
                }

                if (bBreak) break;
                ArrayList ar3 = new ArrayList();
                ar3.AddRange(ar2);
                ar3.Remove(j);
                foreach (int k in ar3)
                {
                    if (bBreak) break;
                    if ((i + j + k) == iEnd)
                    {
                        s1 = "Results = " + i + ", " + j + ", " + k;
                        bBreak = true;
                    }
                }
            }
        }
        Console.WriteLine(s1);

예, 가능합니다. 이 게시물이 여전히 열려 있는지 확실하지 않습니다. 그러나 Excel Solver 추가 기능을하고 싶을 것입니다. 인접한 셀에 1을 사용하여 모든 숫자를 게시하십시오. 그런 다음 원하는 출력 번호를 넣습니다. 그러면 사용 된 모든 숫자는 인접한 "1"을 유지하고 사용하지 않은 것들은 "0"으로 전환됩니다. 그런 다음 그 옆에 "1"이있는 필터 공식 만 사용하십시오.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top