HeYStRanGeR
article thumbnail
[algorithms] ch6. Dynamic programming (Knapsack)
Computer Science/algorithms 2023. 3. 30. 16:13

(23.03.30) algorithms S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2008) 책 읽고 정리하기 http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf 정리한 내용 6.4 Knapsack 예전에 수업들으면서 정리했던 내용: https://hey-stranger.tistory.com/140 Knapsack - 최대 무게가 정해져있는 배낭 안에 value가 최대가 되도록 물건을 담는 방법을 찾는 문제이다. - knapsack은 중복을 허용하여 물건을 선택하는 경우와 중복을 허용하지 않고 물건을 선택하는 경우로 나누어 생각해 볼 수 있다. knapsack with re..

article thumbnail
[알고리즘] Knapsack problem:dynamic programming
Computer Science/algorithms 2021. 10. 14. 23:47

(2021.10.14) 알고리즘 수업들으면서 정리하기 13탄 7주차 보충강의내용- Knapsack problem (보충강의 있는지 모르고 실강 전에 안들었다..) Knapsack problem:dynamic programming 문제: item 여러개가 있는데, 그 item은 각각의 value와 weight를 가진다. knapsack은 W(kg)까지 수용할 수 있다. 이때, knapsack에 담을 수 있는 최대 value가 무엇인가?? 우선, 이 문제를 navie approach로 풀어본다면 각각의 item을 순서대로 넣을지 말지를 결정하기 때문에 2 x 2 x ... x 2=2^n 의 시간이 걸린다. --> O(n^2) Dynamic programming 의 4단계를 거쳐 문제를 풀어볼 수 있다. Ch..

728x90