냅색 알고리즘

냅색 뜻? - 쓰지 않을 때에는 접어서 주머니에 넣을 수 있는 간단한 배낭 냅색은 무언가를 담을 수 있는 배낭을 의미한다. 배낭은 크기에 따라 담을 수 있는 양이 제한되어 있다. 즉, 냅색 알고리즘으로 문제를 풀어야 할때는 제한된 양이 정해졌을 때, 그 양에 효율적으로 채워 넣어서 최대의 가치를 구할때 필요하다. 예를들어  6kg을 담을수 있는 가방이 있다. 아래와 같은 물건 리스트가 있다 1) 가치 4 , 무게 3kg 2) 가치 2 , 무게 1kg 3) 가치 5 , 무게 6kg 4) 가치 6 , 무게 5kg 5) 가치 1 , 무게 2kg 6) 가치 3 , 무게 3kg 여기서 넣을 수 있는 최대의 가치는 몇인가? 이 문제는 DP( Dynamic Programming ) 으로 풀어야 한다. DP 란? 큰 ..

2025.03.29