Baekjoon 12865 평범한 배낭 JAVA

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%2012865

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

해당 문제는 딱 전형적인 냅색 문제였다.

물건수와 물건의 무게 가치가 주어지고, 배낭의 무게가 주어졌을 때

배낭의 무게를 넘지 않으면서 가장 높은 가치를 가지는 경우를 찾는 문제다.

​

해당 문제는 DP를 이용해서 해결했으며, 각각 입력값들은 입력 처리한 뒤

DP 배열을 생성하여 역순으로 반복하는데 이때

물건 수만큼 반복하면서 그 안에서 역순으로 반복하면서 만약 현제 배열 인덱스에서

무게를 뺸 값이 0보다 작다면 지금 반복문을 멈추고 그렇지 않다면

dp 배열에 지금 dp 배열 값과 해당 물건에 무게 값과 해당 물건의 무게 값을 가방에서 뺀 값의 가치 학과

비교를 해서 가장 최댓값을 갱신해 주는 방식으로 진행한다.

​

 

위의 그림처럼 진행된다.