BOJ 문제 링크: https://www.acmicpc.net/problem/12865
12865번: 평범한 배낭
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)
www.acmicpc.net
배낭에 담을 수 있는 무게가 제한 되있고, 각 물건들의 가치와 무게가 주어진다.
이때 배낭에 담을 수 있는 물건들의 가치의 최댓값을 구하는 문제이다.
주어진 물건들을 차례대로 순회하면서 담을지 안담을지를 결정한다. 담았을 경우 현재 배낭에 무게에 담고자 하는 물건의 무게를 추가하여 다음 물건을 결정하는 재귀를 호출하고, 안담았을 경우 현재배낭에 무게 그대로 다음 물건을 결정하는 재귀를 호출한다. 이 두 재귀중 큰 값을 반환하는 경우의 값을 return하면 된다.
코드 원본: https://github.com/sbl133/BOJ/blob/main/%2312865.cpp
GitHub - sbl133/BOJ
Contribute to sbl133/BOJ development by creating an account on GitHub.
github.com
댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!
'Algorithm > BOJ' 카테고리의 다른 글
| [BOJ] 백준 17828번 문자열 화폐 c++ (0) | 2021.09.29 |
|---|---|
| [BOJ] 백준 15686번 치킨 배달 c++ (0) | 2021.09.22 |
| [BOJ] 백준 14503번 로봇 청소기 (0) | 2021.09.04 |
| [BOJ] 백준 9251번 LCS (0) | 2021.09.02 |
| [BOJ] 백준 2812번 크게 만들기 (0) | 2021.09.02 |