1. 문제 요약물건 N개 (각각 무게 W, 가치 V)최대 무게 K가치의 합이 최대가 되도록 물건 선택👉 단, 각 물건은 한 번만 선택 가능 (0/1 배낭)2. 처음 접근 (실패 이유)처음에는 이런 식으로 생각했다:각 물건마다 “최적의 조합 하나”만 저장이전 결과랑 비교해서 갱신하지만 이 방식은 틀렸다.🚨 왜 틀릴까?배낭 문제는 한 시점에서도 여러 선택지가 필요하다.예를 들어:조합가치무게A105B93👉 지금 보면 A가 더 좋아 보이지만👉 나중에 물건을 추가하면 B가 더 유리할 수도 있음즉,❗ “현재 최적 하나만 남기면 미래의 최적을 놓칠 수 있다”3. 핵심 아이디어🔥 DP 정의 dp[j] = 무게가 j일 때 얻을 수 있는 최대 가치4. 점화식현재 물건 (w, v)를 고려할 때: dp[j] = ma..