배낭 문제 (0/1 Knapsack)

문제 설명

N개의 물건과 용량 W인 배낭이 있습니다. 각 물건은 무게와 가치가 있고, 배낭에 담을 수 있는 물건의 최대 가치를 구하세요.

입력 형식

첫 줄: 물건 수 N, 배낭 용량 W

다음 N줄: 무게 가치

출력 형식

최대 가치

제약 조건

• 1 ≤ N ≤ 100
• 1 ≤ W ≤ 10,000

점화식

dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])