알고리즘은 배낭 알고리즘과 비슷합니다 (실제로는 아닙니다).

Question

크기가 n 인 숫자 집합입니다 (n> 100이라고 가정).

하드 한계 x도 있습니다.

내가 원하는 것은 내 세트에서 가변 개수의 요소를 가져와 합계가 < = x이지만 가능하면 x에 가까워 지도록 이러한 요소의 조합을 찾는 것입니다.

분명히 나는 ​​brute-force 접근 방식을 사용하고 싶지 않다. 효율적인 알고리즘이이 문제를 해결할 수 있는가?

Answer 1

이 이미 있거나 this PDF

에 41 페이지에서 사용할 수있는 텍스트에서 논의 될 수있는 자주 사용하는 의사 다항식 배낭 알고리즘에 매우 적합 보인다