#Knapsack Problem
Programming
2017. 10. 16. 23:32
학부생 때 제대로 이해 못했던 알고리즘을 지금에서야 공부하고 있다. 무엇보다 기본이 가장 중요하니까- 알고리즘은 간단하지만, 확인하는 절차가 상당히 오래 걸렸다.배낭 문제의 목적은 n개의 무게와 가격을 가진 각각의 아이템 중에서,배낭의 용량을 초과하지 않으면서 가격이 최대가 되는 아이템의 부분집합을 구하는 것이다.대략적인 설명과 알고리즘은 'Youtube 권오흠님의 알고리즘-동적계획법 영상'의 슬라이드로 대체한다. 설명이 조금 부족해 보일 수도 있지만, 동적 계획법을 잘만 이해하고 있다면 어렵지 않게 이해할 수 있을 것이라고 본다.알고리즘이 정말 너무 간단하다....알고리즘의 핵심은 결국 'M'이라는 배열에 memoization 작업을 하는 것이다. 아래는 내가 직접 만들어서 푼 문제이다.def knap..
