JUNGOL 1077 배낭채우기1 JAVA

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=357&sca=99&sfl=wr_subject&stx=%EB%B0%B0%EB%82%AD

JUNGOL

 

https://github.com/JUNGSOONIL/JAVA/blob/main/JUNGOL%201077

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

 

해당 문제는 냅색 문제다. 하지만 종류당 하나만 담을 수 있는 것이 아니라 여러 개도 담을 수 있다.

​

처음의 문제를 보고는 어떤 식으로 풀지 생각을 좀 하다가

하나씩 배열에 넣어가면서 비교를 하면 되겠다고 생각했고,

만약에 현재 배열의 인덱스에서 해당 보물 무게를 뺀 게 0보다 크면

dp 배열에 값을 넣어주는데 이때 max를 이용해서 현재 무게에서 해당 보물 무게를 나눈 값의 가치를 곱한 값 더하기

현재 무게에서 해당 보물 무게를 나눈 나머지 값에 해당하는 dp 값을 더한 것과

현재 dp 값 중에서 큰 값을 저장하는 식으로 해결했다.

dp[j] = Math.max(j/W[i] * V[i] + dp[j%W[i]], dp[j]);