배낭문제1 0-1 Knapsack Problem 0-1 Knapsack Problem 다이나믹 프로그래밍의 대표적인 문제라 할 수 있는 문제입니다. 무게 제한이 있는 배낭에 가치가 최대가 되도록 짐을 넣는 문제인데, 넣을 수 있는 짐을 쪼갤 수 있느냐 없느냐에 따라 ① 분할가능 배낭문제(Fractional Knapsack) ② 0-1 배낭문제(0-1 Knapsack problem) 으로 나눠집니다. 분할가능 배낭문제는 Greedy 알고리즘을 활용하여 최적으로 풀이가 가능하지만 분할이 불가능한 0-1 배낭문제는 모든 경우의 수를 봐야합니다. 0-1 배낭문제를 최적화 하기 위해 다이나믹 프로그래밍, Tabulation이 활용됩니다. 0-1 배낭문제에 (가치, 무게) 형태의 Tuple 이 저장된 리스트가 Input으로 들어온다고 하면, 아래와 같은 테이블을.. 2020. 10. 4. 이전 1 다음