백준 12865번 평범한 배낭 C++

 

1. 문제 설명

 

배낭 문제

여행에 가지고 갈 배낭을 최대한 가치 있게 싸려고 한다.

필요한 물건 N개가 있고, 가방에 넣을 수 있는 최대무게 K가 주어진다.

각 물건은 무게 w와 가치 v를 가지는데, 해당 물건을 잘 배낭에 넣어서 가져가면

가치 v만큼 즐길 수 있다. 가장 가치 있게 여행을 즐길 수 있도록 배낭을 싸는 프로그램을 작성하는 문제이다.

 

우선 입력값이 꽤 많으니 

해당 코드를 넣으며 시작하고

 

어떻게 하면 가치있게 넣을 수 있는지에 대한 점화식을 찾는다 dp 문제이다.

 

예시를 보면 무게와 가치가 같이 들어오기 떄문에 vector pair로 저장을 해주고

 

vector<int> dp 를 k + 1의 크기로 값을 0으로 선언하여 준다.

각 dp[j] 무게 j일 떄 만들 수 있는 최대 가치를 구해야 하며

0 부터 최대 무게 k까지 값을 저장해야 하기 때문에 k + 1로 선언한다.

 

j = k 최대무게로 하고 w 까지 --를 하는 것은

j >= w인 경우만 배낭에 물건을 넣을 수 있으므로 그렇게 반복해야 하며

그 이상은 반복할 필요가 없다. 배낭에 넣을 수 없기 때문이며,

j--로 뒤에서부터 반복하는것은 같은 물건을 중복해서 쓰는걸 방지하기 위해서이다.

 

w = 현재 물건의 무게, v = 현재 물건의 가치

dp[j] = 무게 j일 때 최대 가치를 저장, dp[j -w] + v = 이 물건을 넣었을 경우 새로 얻을 수 있는 가치 

max 함수를 통해 이전 상태 dp[j -w]를 이용하여 현재 상태 dp[j]를 갱신하며 효율적으로 접근한다.