백준 문풀

배낭 알고리즘

조강학 2024. 11. 9. 23:57

n개의 물건과 배낭이 있고, 물겅에는 가치와 무게 값이 존재한다. 

배낭에는 최대 용량이 존재하고 이 용량 안에서 담을 수 있는 물건의 최대 가치를 찾는다.

 

다이나믹 프로그래밍 , 즉 큰 문제를 작은 문제로 쪼개 푸는 것으로 해결 가능하다.

dp는 이차원 배열로 작성하고 

dp [ 현재 탐색하는 물건 ] [ 가방의 남은 공간 ] = 최대 가치

 

가방 최대 5키로 0 번 물건/3kg 1번 물건 2 번 물건 3 번 물건 4 번 물건
0키로          
1키로          
3키로          
4키로          
5키로          

 

이런 형태의 표를 생각 할 수 있다

 

..

d[1][6] 은 1번 물건을 담으려 하는데 남은 공간이 6키로라는 의미다.

1번 물건이 3키로에 3달러라 했을 때, 배낭의 최대 가치는 d[i][3] 중 최대 값 +3 달러 일 것이다.


d[ i ][ j ] = max ( d[ i−1 ][ j ] , ( i번 물건의 가치 ) + d[ i − 1 ][ j − ( i번 물건의 무게 )])


 볼 때마다 새로운 수식이다. 머리에 전혀 남지 않음.

풀때 마다 찾아보는데 그럼에도 문제를 틀린다.ㅜㅋ

d[i−1][j]d[i-1][j] : ii번 물건을 선택하지 않은 상태에서의 최대 가치

(i번 물건의 가치)+d[i−1][j−(i번 물건의 무게)](\text{i번 물건의 가치}) + d[i-1][j - (\text{i번 물건의 무게})] : ii번 물건을 선택하는 경우의 최대 가치

'백준 문풀' 카테고리의 다른 글

백준 2468  (1) 2025.01.01
백준 9084  (0) 2024.11.10
백준 2656 전깃줄  (0) 2024.11.05
백준 1920 수 찾기  (0) 2024.09.30
백준 2295 세 수의 합  (0) 2024.09.30