Knapsack 문제

어떤 아이템을 나타내는 배열(하위 배열에는 두 개의 정수를 가진 배열)이 제공됩니다. 첫번째 정수는 아이템의 값이며 두번째 정수는 아이템의 무게입니다. 그리고 배낭의 최대 용량을 나타내는 정수 capacity를 입력 받습니다.

우리의 목표는 아이템들의 무게의 합계가 배낭의 최대용량을 넘지 않게 배낭에 집어넣는 것과 동시에 아이템들의 값의 합계를 최대화하는 것 입니다.

선택한 아이템들의 최대값을 만들수 있는 아이템의 배열을 반환하는 함수를 작성하세요.

배낭의 최대값을 만드는 아이템들의 조합이 여러 개일 경우 함수는 그 중 한 항목을 반환하면 됩니다.

예제 1

입력

items = [[1, 2], [4, 3], [5, 6], [6, 7]]
capacity = 10

출력

[[4, 3], [6, 7]]

Test Case 1

Input

items = [
    [1, 2],
    [4, 3],
    [5, 6],
    [6, 7]
]
capacity = 10

Output

[
    [4, 3],
    [6, 7]
]

Test Case 2

Input

items = [
    [1, 2],
    [4, 3],
    [5, 6],
    [6, 7]
]
capacity = 9

Output

[
    [4, 3],
    [5, 6]
]

Test Case 3

Input

items = [
    [10, 2],
    [4, 3],
    [5, 6],
    [6, 7]
]
capacity = 9

Output

[
    [10, 2],
    [6, 7]
]

Test Case 4

Input

items = [
    [1, 2],
    [4, 3],
    [5, 6],
    [6, 7]
]
capacity = 100

Output

[
    [1, 2],
    [4, 3],
    [5, 6],
    [6, 7]
]

Test Case 5

Input

items = [
    [1, 2],
    [4, 3],
    [5, 6],
    [6, 7]
]
capacity = 1

Output

[]

My Answer
Lecture

Output

W+코딩 알고리즘 강의

프로그래밍을 이해하는데 꼭 필요한 알고리즘을 쉽고 빠르게 배울 수 있도록 준비한 강의 입니다.

코딩테스트를 준비하시는 분, 알고리즘에 대해서 전반적으로 공부하고자 하는 분들을 위해 꼭 필요한 토픽을 모아서 기초부터 고급 문제까지 단계적으로 구성되어 있습니다.

프로그래밍 언어는 JavaScript · Java · Python · C++ · C# 을 이용하여 브라우저에서 직접 프로그램을 작성 및 실행할 수 있으며, 알고리즘 강의를 통해 주어진 문제를 응용하여 다양한 솔루션을 작성하고 온라인에서 바로 테스트하면서, 알고리즘에 대해 좀 더 깊은 이해를 도와 드립니다.

알고리즘 수강신청

코딩테스트 문제해설

온라인으로 코딩문제 풀면서 학습하는 사이트를 찾고 계신가요? W+코딩에서는 코딩공부 하면서 헷갈리는 부분을 알기 쉽고 정확하게 알려드립니다.

알고리즘 코드해설

바이너리트리, 링드리스트, 그래프, 다이나믹 프로그래밍, 그리디 등등등... JavaScript, Java, Python, C++, C# 솔루션을 정확하고 알기 쉽게 설명해 드립니다.