knapsack

1. Knapsack Knapsack 문제는 조합 최적화 문제의 일종으로 주어진 물건들의 가치와 무게, 그리고 배낭의 총용량이 주어졌을 때, 배낭에 넣은 물건들의 가치의 합이 최대가 되도록 하는 물건들의 부분집합을 찾는 문제이다. 동적 계획법(Dynamic Programming)으로 풀 수 있다. 2. 공간 복잡도 개선 기존의 동적 계획법(DP)은 O(NK)의 공간 복잡도를 가지고 있다. (여기서 N은 물건의 개수, K는 배낭의 최대 무게를 … 더 읽기