Knapsack - 제한 용량에 최대 가치 채우기
Knapsack 문제 일반화10kg 배낭에 넣을 수 있는 물건이 4개가 있고 각 물건의 무게와 가치는 다음과 같다.무게 : 5, 4, 6, 3가치 : 10, 40, 30, 50여기서 각 물건은 넣거나 넣지 않을 수 있다. 최대 가치를 구해야 하므로 가장 작은 문제 부터 최대 가치를 만들어서 10kg 문제까지 해결해보자여기서 가장 작은 문제는 1kg 배낭에 채울 수 있는 최대 가치라고 정의하자. 1. (5, 10) 의 물건1 ~ 4kg 배낭엔 채울 수 없으므로 가치는 05kg 배낭으로 가치는 10 2. (5,10) (4,40) 의 물건1 ~ 3kg 배낭엔 채울 수 없으므로 가치는 04 ~ 8kg 배낭엔 (4, 40)을 채울 수 있으므로 가치는 409 ~ 10kg 배낭엔 (4, 40), (5, 10) 추가할..
2024. 8. 23.
