12865 평범한 배낭1 *[Python] 12865-평범한 배낭 1. 개념 정의 - N: 물품의 수(1 ≤ N ≤ 100) - K: 버틸 수 있는 무게(1 ≤ K ≤ 100,000) - W: 물건의 무게(1 ≤ W ≤ 100,000) - V: 물건의 가치(0 ≤ V ≤ 1,000) 2. 문제 이해 - 준서는 여행을 떠나며 N개의 물건을 챙긴다. 각 물건은 (무게 W, 가치 V)를 가진다. 배낭에 넣은 물건의 V 만큼 준서는 즐길 수 있다. 다만 최대 K무게까지만 들고 다닐 수 있다. 이제 준서가 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 구해야 한다. 3. 로직 짜기 1. 가치 V를 내림차순으로 정렬 후 K를 넘지 않게 해서 가방에 넣으면? - 최대 가치의 무게가 지나치케 클 경우 최적화 불가능 2. 무게당 가치(가치/무게)가 큰 순으로 내림차순 정렬 후 차례대로.. 2020. 10. 27. 이전 1 다음