knapsack

배낭 문제(Knapsack)배낭문제는 여러 물건이 있을 때, 특정 조건을 만족하는 조합을 구하는 문제이다. 이를테면, 물건 n개가 있고 배낭에 m 만큼 채울 수 있을 때, 최대 무게를 초과하지 않는 범위 내에서 아이템들을 담을 수 있다. 각 아이템은 1개만 사용할 수 있고, 배낭의 무게 제한을 초과하지 않도록 아이템을 선택하여 배낭에 담아야 한다. 목표는 배낭에 담은 아이템들의 가치를 최대화하는 것이다. 문제 정의입력N: 아이템의 개수W: 배낭의 최대 무게각 아이템에 대해w_i: 아이템 i의 무게v_i: 아이템 i의 가치출력배낭의 최대 무게를 초과하지 않으면서 담을 수 있는 아이템들의 가치를 최대화한 값해결 방법0/1 배낭 문제를 해결하는 일반적인 방법은 동적계획법을 사용하는 것이다. DP 테이블을 사용..