무한 배낭
골드 IV의견: 0
\(N\) 종류의 물건이 있다. \(i\) 번째 종류의 물건은 무게가 \(w_i\), 가치가 \(v_i\) 이며, 각 종류를 원하는 만큼 여러 번 담을 수 있다(개수 제한이 없다).
용량(최대 무게)이 \(W\) 인 배낭에 물건들을 담되, 담은 물건들의 무게의 합이 \(W\) 를 넘지 않도록 한다. 이때 담을 수 있는 가치의 합의 최댓값을 구하여라.
아무 물건도 담지 않아도 되며, 이 경우 가치의 합은 \(0\) 이다.
\(1 \le N \le 100\)
\(0 \le W \le 10^5\)
\(1 \le w_i \le 10^5\)
\(0 \le v_i \le 1000\)
첫째 줄에 물건의 종류 수 \(N\) 과 배낭의 용량 \(W\) 가 공백으로 구분되어 주어진다.
다음 \(N\) 개의 줄에 각각 두 정수 \(w_i\) 와 \(v_i\) 가 주어진다.
배낭에 담을 수 있는 가치의 합의 최댓값을 첫째 줄에 출력한다.
4 7
6 13
4 8
3 6
5 12
14
무게 \(7\) 까지 담을 수 있다. 무게 \(4\)(가치 \(8\))과 무게 \(3\)(가치 \(6\))을 하나씩 담으면 무게 \(7\), 가치 \(14\) 로 최대다.
2 10
3 4
5 7
14
무게 \(5\) 짜리를 두 번 담으면 가치 \(14\), 무게 \(3\) 을 세 번 + 여분으로는 무게 \(3\) 세 개(가치 \(12\)) 등보다 좋다. 답은 \(14\).
1 5
6 100
0
유일한 물건의 무게가 \(6\) 으로 용량 \(5\) 를 넘어 아무것도 담을 수 없으므로 최대 가치는 \(0\).
riseoj 작성
출처 Original
평가 및 의견
무한 배낭
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
무한 배낭