ref: https://www.acmicpc.net/problem/12865
문제 해석
처음에는 물건 대비 가치로 나눠 해당 무게가 얼마만큼의 비율로서의 가치를 보유하고 있는지에 대해서 접근하려고 했는데 그렇게 하니 소수점 단위로 나와 출력값이랑 다르게 나왔다.
따라서 문제에서 요구하는 바와 같이 주어진 해당 무게와 가치의 정보로만 가지고 배낭에 무개를 넣어 최대 가치를 추출 해야 한다.
결국 목표는 모든 무게에 대해서 최대가치를 저장하고
각 물품의 번호 i에 따라 테이블을 갱신 할 수 있다
그리고 우리가 구하는 최종 답은 테이블[i][j] 값이다.
코드해석
우선 내가 담아야 할 무게 종류의 수와 배낭의 최대 무게를 입력 받는다.
그리괴 최대 가치를 추출하기 위한 전부 0 으로 구성된 테이블을 생성한다.
그리고 어차피 무게의 종류 만큼 따져줄 것이기에 for문을 1부터 n+1 만큼 돌리고
해당 무게와 무게의 가치를 입력한다.
그리고 해당 무게들이 배낭 무게 만큼 채워 나가야하니 배낭 무게에 해당하는 for문을 입힌다.
if j < weight :
# 바로 위에 위치하는 가치를 물려 받음.
dp[i][j] = dp[i-1][j]
이부분은 애초에 넣으려는 무게보다 배낭의 무게가 작거나 초과되면 집어 넣을 수 없으니 바로 위의 존재하는 값을 그대로 물려 받는다
( Ex : 무게가 5이면 배낭의 무게가 4 일 때 까지는 넣을 수 없으니 0 으로 되거나 무게가 3이 앞에 들어가더라도 나머지 2는 5로 채울 수 없으니 3의 가치만큼 불려 받는 것이다.)
그리고 만약에 배낭의 무게가 더 크다면 ! 즉, 남은 공간이 있어 해당 무게가 들어갈 여유공간이 있다면 기존에 들어있던 가치와 새롭게 들어갈 무게의 가치를 더한게 기존의 가치보다 더 크다면 갱신을 해주고 그렇지 않다면 ( 남은 공간에 해당 무게를 넣어도 기존 가치보다 못함) 기존의 가치를 유지해주는 것이다 !
즉, 핵심은 해당 무게별로 최대값을 추출하는 것인데 애초에 배낭의 무게를 뛰어넘어버리면 계산을 할 필요가 없고 만약에 여유 공간이 존재한다면 기존의 들어있던 가치와 내가 들어가서 새로운 가치를 만들었을 때의 가치의 합이 기존의 기록을 갱신할 수 있다면 새로운 가치로 설정해주는 것이다
