배낭 카운팅
골드 III의견: 0
무게가 각각 \(w_1, w_2, \dots, w_N\)인 물건 \(N\)개가 있다.
정확히 \(K\)개의 물건을 골라 배낭에 넣되, 총 무게가 \(W\) 이하가 되는 경우의 수를 구하여라.
- \(1 \le N \le 40\)
- \(0 \le K \le N\)
- \(0 \le w_i \le 10^{14}\)
- \(0 \le W \le 10^{15}\)
첫째 줄에 물건의 수 \(N\), 최대 무게 \(W\), 선택할 물건 수 \(K\)가 공백으로 구분되어 주어진다.
둘째 줄에 각 물건의 무게 \(w_1, w_2, \dots, w_N\)이 공백으로 구분되어 주어진다.
조건을 만족하는 경우의 수를 출력한다.
8 10 3
3 1 4 1 5 9 2 6
23
무게가 \(10\) 이하이고 \(3\)개짜리 부분집합의 수를 구한다. \(\{1,1,5\}=7\), \(\{1,1,6\}=8\), \(\{1,2,5\}=8\), \(\{1,2,6\}=9\), \(\{1,3,4\}=8\), \(\{1,3,5\}=9\), \(\{1,3,6\}=10\), \(\{1,4,5\}=10\), \(\{2,3,4\}=9\), \(\{2,3,5\}=10\), \(\{1,4,4\}=9\) 등 여러 가지가 있다.
4 10 2
5 5 5 5
6
\(4\)개 중 \(2\)개를 고르는 경우 \(\binom{4}{2}=6\)가지이며 모두 무게 \(10\)이므로 답은 \(6\)이다.
riseoj 작성
출처 Original
평가 및 의견
배낭 카운팅
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
배낭 카운팅