관리 메뉴
목록2024/09/27 (1)
미소를뿌리는감자의 코딩
Knap Sack
1. 개요이번에는 knap sack 문제에 대해서 알아보았다.knap sack은 보석의 무게와 가격이 있을 때, 어떻게 최대로 높은 가격의 보석을 제한된 무게 안으로 챙길 수 있는지에 대한 문제이다.이를 dynamic programming으로 코드를 작성해서 해결하게 된다.0, 1, 2, 3, 4, 5 는 가방의 최대 무게가 0일 때, 1일 때, ...을 의미한다. 이전 보석을 확인하고, 다음 보석을 확인할 때는 2가지 경우가 생기게 된다.보석이 남은 가방의 무게를 초과할 때보석을 가방에 넣을 수 있을 때 -> 보석을 가방에 넣을 것인가, 넣지 않을 것인가.로 나뉘게 된다. 이런 점화식을 기반으로 코드를 작성하게 된다. 점화식에서 B[i][w] = max(B[i-1][w], B[i][w - wi] + v..
코딩 이야기
2024. 9. 27. 23:04