문제

1. 도둑이 배낭에 넣을 수 있는 최대 보석 무게

fractional knapsack problem

1. 그리디 알고리즘
   1. value per pound(v/w) 순으로 정렬

0-1 Knapsack problem

1. brute force
   1. 모든 경우를 계산하여 가장 큰 경우
   2. time complexity: O(2^n)
2. 그리디
   1. 해당 문제 해결 불가

DP

1. B[k,W]: Sk까지의 최대
   

2. 코드

   Time complexity: O(n*W)

   

Branch and Bound

1. node
   
   
2. bound
   
3. promising & non-promising
   

   진행 상황