Code NaviCode Navi

말로 푸는 알고리즘

핵심 문제로 풀이 흐름을 다듬습니다.

06/ 6

성장 단계 6/6

배송 상자 최대 가치 채우기

06

배송 상자 최대 가치 채우기

Hard

무게 제한이 있는 배송 상자에 상품을 한 번씩만 담아 최대 가치를 만들어야 합니다. 어떤 상태를 기억해야 같은 상품을 두 번 담지 않는지 설명해보세요.

핵심 포인트

용량별 최선을 먼저 정의하고 중복 없이 갱신하는 게 핵심입니다.

예시

  • 입력:

    w=[2,3,4], v=[4,5,6], cap=5

    출력:

    9

  • 입력:

    w=[1,3,4], v=[15,20,30], cap=4

    출력:

    35

조건

상품 개수 n >= 1
무게와 가치는 양수

풀이 적기

풀이 흐름을 짧게 적어보세요.