정수 목록을 사용하여 주어진 합계에 가장 가까운 해결책을 찾기 위해 어떤 알고리즘을 사용해야합니까?

Question

내 문제는 다음과 같습니다.

정수 목록이 A [2013, 54, 3, 32 1, 23 ...]

가 있다고 가정 해 봅시다.

주어진 숫자와 동등하거나 가장 가까운 합계를 갖기 위해 내가 함께 추가 해야하는 숫자를 찾아야하는 가장 좋은 전략은 무엇입니까?

분명히 항상 무차별의 힘 법이 있지만 더 적합한 것이 있는지 아는 데 관심이 있습니다.

Answer 1

자동차에 수하물을 포장 할 때 먼저 가장 큰 항목을 넣은 다음 주변의 작은 항목에 맞 춥니 다. 유추로, 귀하의 문제에 대한 휴리스틱 접근 방식은 가능한 한 크게 큰 것과 함께 가능한 한 큰 세트의 구성원으로 시작하는 것입니다. 그런 다음 현재 총 합계와 대상의 차이점을 반복하십시오. 이것은 탐험 알고리즘

세트가 $ \ {2,3,5,8,13,21, 34 \} $ 을 $ 32 $ , $ 21 $ ( $ 32 $ ), $ 8 $ (이것이 )를 누른 다음 $ 3 $ 을 추가하십시오.

욕심 많은 알고리즘은 빠르고 간단하지만 항상 최상의 솔루션을 제공하지는 않습니다. 예를 들어, 세트가 $ \ {1, 5, 26, 26 \} $ 이고 대상은 $ 30 $ @ $ 26 + 1= 27 $ 은 $ 26 + 1= 27 $ $ 23 + 5 + 1= 29 $ .

Answer 2

문제는 NP 완성이지만, 주어진 숫자의 가치에서 다항식이며 다항식이 매우 낮습니다. 관련된 숫자가 큰 경우에만 어렵습니다.

가장 작은 것부터 가장 큰 것까지 정렬하고 숫자가 맞지 않을 때까지 추가 할 때까지는 영리하지 않습니다. 왜냐하면 적합하지 않은 다소 많은 숫자가 될 것이므로 원하는 합계에 가깝지 않을 것입니다. 가장 큰 곳에서 가장 작은 것으로 정렬하고 가장 큰 숫자를 먼저 추가하는 것이 훨씬 낫습니다.

이제 SUM 닫기 항목이있는 항목이 있으면이를 개선하려고 시도 할 수 있습니다. 예를 들어 SUM이 너무 작아 지지만 가장 작은 사용되지 않은 항목은 317이면 목록에 X 항목 x 및 목록에없는 항목이있는 경우 y는 x보다 약 200 이하의 항목을 사용해야합니다. - x에 대해 x를 스왑, 크기 317 항목을 추가하십시오. 간단한 알고리즘조차도 당신이 좋은 개선을 찾을 수 있습니다.

완전히 다른 방법 : 원하는 합계가 매우 큰 S (같은 수조)로 s (많은 수조)를 사용하도록하십시오. 그런 다음 1,000,000 명을 선택하고 (s '/ s)에 관여하는 모든 숫자를 곱하고 1,000,000에 가까운 합계가있는 항목을 찾은 다음 원래 항목을 선택할 수 있습니다. 1,000,000에 가깝게 몇 가지 합계를 시도하십시오.

Answer 3

@Yuval의 댓글 덕분에 나는 정확히 내가 찾고있는 짐 문제로 이어졌다.

Wikipedia 에서이 NP 완전한 문제로 제안 된 해결책의 대부분을 이해하지 못했지만, 나는 빠르지 만 완전히 신뢰할 수없는 접근법을 생각했습니다 :

사용 가능한 정수 목록을 가장 작은 것으로 정렬하고 원하는 조건이 충족 될 때까지 추가를 시작합니다.

정수 세트의 두 구성원 간의 모든 차이점이 다르지 않으면이 접근 방식은 아마도 최상의 솔루션을 제공 할 것입니다.