본문 바로가기

카테고리 없음

[2020모각코] 4회차 2021.01.13

이 문제를 해결하기 위해 dp라는 배열을 생성하였다. dp배열은 i번째 값을 증가하는 부분 수열의 마지막 값으로 가지는 부분 순열의 최댓값을 저장하는 배열이다. 따라서 dp배열이 최대인 경우 증가하는 부분 수열이 가장 큰 값을 가지게 된다.  i번째 값이 이전에 있는 값보다 크면 이전의 dp값들과 비교하여 그 중 가장 큰값에 i번째 값을 추가하여 dp를 구하는 식으로 프로그램 하였다.

 

이 문제를 해결하기 위해선 모든 물품의 경우의 수를 따져봐야 한다고 생각하였다.

가방의 무게를 x축으로 , 포함 될 수 있는 물건을  y축으로 삼는  dp라는 2차원 배열을 만들어 모든 경우의 수를 저장하였다. i번째의 물건이 가방에 포함 될 수 있는 경우 이전 가치의 값과 i번째 물건이 포함된 가치의 값 중 최대값으로 dp의 값을 정하여 문제를 해결하였다.