냅색 경우의 수
시간 제한1초메모리 제한128 MB
무게가 큰 최대 30개의 물건과 용량 제한이 주어질 때, 총 무게가 용량 이하인 부분집합의 개수를 구합니다.
문제
세준이는 N개의 물건과 최대 무게 C까지 담을 수 있는 가방 하나를 가지고 있다.
각 물건은 한 번씩만 선택할 수 있으며, 아무것도 넣지 않는 경우도 하나의 방법으로 센다. 선택한 물건들의 무게 합이 C 이하가 되도록 가방에 넣는 방법의 수를 구하시오.
입력
첫째 줄에 물건의 수 N과 가방의 최대 허용 무게 C가 주어진다. N은 30 이하의 자연수이고, C는 10^9 이하의 음이 아닌 정수이다.
둘째 줄에는 N개 물건의 무게가 주어진다. 각 무게는 10^9 이하의 자연수이다.
출력
무게 합이 C 이하가 되도록 물건을 고르는 방법의 수를 출력한다.