혜택

Ready to put your newfound language skills into use? Get 40% off CodeCrafter's real-world proficiency projects!

할인 혜택 받기

트랙

Emacs Lisp

연습 문제

배낭 문제

보통

소개

Lhakpa는 셰르파 산악 가이드이자 포터예요. 몇 달간의 꼼꼼한 준비 끝에, Lhakpa가 일하는 원정대가 곧 떠나려 해요. 그녀는 베이스 캠프까지 운반한 물건의 값어치만큼 보수를 받아요.

그녀 앞에는 값어치와 무게가 각각 다른 여러 물건이 있어요. Lhakpa는 기꺼이 그 물건을 모두 가져가고 싶지만, 배낭에는 담을 수 있는 무게가 정해져 있어요.

지침

여러분의 과제는 배낭이 담을 수 있는 무게를 고려하면서, 선택한 물건들의 가치 합이 최대가 되도록 어떤 물건을 가져갈지 정하는 거예요.

물건은 목록으로 주어져요. 각 물건에는 무게와 가치가 있어요. 주어지는 가치는 모두 양수예요. Lhakpa는 각 물건을 하나씩만 가져갈 수 있어요.

예를 들어볼까요:

Items: [
  { "weight": 5, "value": 10 },
  { "weight": 4, "value": 40 },
  { "weight": 6, "value": 30 },
  { "weight": 4, "value": 50 }
]

Knapsack Maximum Weight: 10

위 예시에서 첫 번째 물건은 무게가 5이고 가치가 10이며, 두 번째 물건은 무게가 4이고 가치가 40이에요. 나머지도 마찬가지예요. 이 예시에서 Lhakpa는 가치를 최대로 하려면 두 번째와 네 번째 물건을 가져가야 해요. 이 경우 가치는 90이 돼요. 배낭의 무게 제한이 10이기 때문에 Lhakpa는 90보다 더 많은 가치를 얻을 수 없어요.