효팍이의 프로그래밍

0-1 배낭 문제 분할 가능 배낭 문제와 달리 짐을 쪼갤 수 없는 0-1 배낭 문제를 풀이해 보자. 이 문제는 '탐욕 선택 속성'이 있는 문제가 아니며 '중복된 하위 문제들' 속성을 갖고 있으므로 다이나믹 프로그래밍으로는 풀 수 있다. 단가 순으로 그리디하게 배치해서 풀이했던 분할 가능 배낭 문제와 달리, 0-1 배낭 문제는 짐을 쪼갤 수 없다. 이 경우 모든 경우의 수를 계산해야 한다. 먼저, 입력값으로 짐을 정의하고 zero_one_knapsack() 풀이 함수를 호출한다. cargo = [ (4, 12), (2, 1), (10, 4), (1, 1), (2, 2), ] print(zero_one_knapsack(cargo)) zero_one_knapsack() 함수는 다음과 같이 정의한다. def z..