일반적으로 배낭문제는정해진 무게 안에 가장 가치 있는 물건을 고르는 것 이다. 이번 포스팅에서는 배낭 문제의 3가지 유형 (0/1, 무한, 개수제한)에 대해 이해해보려한다.사실 배낭문제도 2차원 배열을 활용한 DP 문제다 따라서 제일 먼저 문제를 보고 할 일은 최적 부분 구조 + 부분 반복 문제 확인하는 것이다. 이전 상태 유지 + 개수 제한 일 때는 중복 사용 방지를 위해 2차원 배열을 사용이 유리할 수 있다. 개수제한일 때를 생각해보면 1차원 배열 사용시 중복 사용될 가능성이 있다. 제한이 2개일때 배낭 무게 최대 무게 6아이템 1개에 대하여 무게 2, 가치 10 이라하면dp = {0, 0, 10, 0, 20, 0, 30} 이런식으로 3번 같은 아이템을 사용해 버린다. 때문에 2차원 배열로 같은..