7184 : 부분합 백트래킹
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
N개의 자연수가 주어집니다. 이 중 일부를 선택해 합을 구할 때, 한계치 S를 넘지 않으면서 가장 큰 합을 구하는 프로그램을 작성하십시오.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 원소의 개수 N과 한계치 S가 주어집니다. (1 ≤ N ≤ 30, 1 ≤ S ≤ 1,000,000,000)
둘째 줄에 N개의 자연수가 공백으로 구분되어 주어집니다.
둘째 줄에 N개의 자연수가 공백으로 구분되어 주어집니다.
출력 설명
S를 넘지 않으면서 가장 큰 부분집합의 합을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 10
1 2 3 4 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
10도움
모든 원소의 합 {1, 2, 3, 4} 또는 {1, 4, 5} 등의 합이 정확히 10이 되어 한계치 S 이하의 최대 합입니다.