목록배낭문제 (1)

daniel7481의 개발일지

[BOJ] 23061 백남이와 여행 준비

[출처: 백준 온라인 저지] 문제 방학을 맞은 귀여운 백남이는 여행을 떠날 준비를 하고 있다. 백남이는 여행에 필요하다고 생각하는 필수품 N$N$개를 가지고 있다. 각 물건은 무게 W$W$와 가치 V$V$를 가진다. 그리고 백남이는 물건을 담을 가방 M$M$개를 가지고 있는데, 각각의 가방은 최대 Ki$K_i$만큼의 무게를 견딜 수 있다. MBTI가 J(판단형)인 백남이는 효율성을 중요하게 여기기 때문에, 가장 효율적으로 짐을 싸지 않으면 여행을 출발할 수 없다. 백남이가 정의한 효율성은 (가방에 담긴 물건의 가치의 합) / (가방이 견딜 수 있는 최대 무게)이다. 가방과 물건의 정보가 주어졌을 때, 가장 효율적으로 짐을 싸기 위해 필요한 가방이 무엇인지 알아내자. 가방은 한 개만 선택할 수 있으며, 최..
BOJ 2022. 1. 29. 16:58
이전 Prev 1 Next 다음