Knapsack1

• 

  210707 DP - 배낭 문제 (Knapsack Problem) 배낭 문제 (0/1 Knapsack Problem) 배낭 문제란 배낭에 담을 수 있는 무게의 최대값이 정해져 있고, 일정한 가치와 무게가 정해져있는 짐들을 배낭에 닮을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. 0/1 knapsack = 물건 못 쪼갬 Fraction knapsack = 물건 쪼갤 수 있는 문제 사실 kanpsack 문제는 dp에 있어야... 예시 문제 해결법 시간 복잡도 , 공간복잡도 미가공 필기(알고리즘) 2021. 7. 8.