혜택

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

할인 혜택 받기

트랙

WebAssembly

연습 문제

배낭 문제

어려움

소개

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보다 더 많은 가치를 얻을 수 없어요.

WebAssembly 관련 참고 사항

항목들은 선형 메모리를 통해 전달되고, 첫 번째 항목은 오프셋 0에 있어요. 각 항목은 32비트 정수 한 쌍으로 표현돼요. 쌍에서 첫 번째 숫자는 weight이고, 두 번째 숫자는 value예요.

예를 들어, 두 개의 항목으로 이루어진 배열이 있고 첫 번째 항목이 weight=1, value=2, 두 번째 항목이 weight=5, value=8이라고 해봐요. 그러면 이 배열은 메모리에서 이렇게 보여요:

| 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 |
| - item 1 weight - | -- item 1 value - | - item 2 weight - | -- item 2 value - |
|0x01,0x00,0x00,0x00|0x02,0x00,0x00,0x00|0x05,0x00,0x00,0x00|0x08,0x00,0x00,0x00|

원한다면, 입력에 사용되는 선형 메모리의 주소를 덮어써도 돼요.