혜택

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

할인 혜택 받기

트랙

Haskell

연습 문제

배낭 문제

보통

소개

Bob은 도둑이에요. 몇 달간의 치밀한 계획 끝에, 마침내 고급 매장의 보안 시스템을 뚫는 데 성공해요.

그 앞에는 저마다 값과 무게가 있는 물건들이 많이 놓여 있어요. Bob은 그 물건들을 모두 가져가고 싶지만, 배낭에는 담을 수 있는 무게가 정해져 있어요. Bob은 고른 물건들의 총 가치가 최대가 되도록 어떤 물건을 가져갈지 신중하게 따져봐야 해요.

지침

배낭의 최대 무게를 고려해서, 고른 물건들의 총 가치가 최대가 되도록 어떤 물건을 담을지 정하는 것이 이번 과제예요.

물건들은 배열로 주어져요. 각 물건에는 무게와 가치가 있어요. 주어지는 가치는 모두 양수예요. Bob은 각 물건을 하나씩만 담을 수 있어요.

예를 들어:

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이에요. 이런 식이죠. 이 예에서는 가치를 최대로 만들기 위해 Bob이 두 번째와 네 번째 물건을 담아야 해요. 이 경우 가치는 90이에요. 배낭의 무게 제한이 10이라서 Bob은 90보다 더 큰 가치를 얻을 수 없어요.