1차원 냅색 코드
- 서로 다른 물건을 1번씩만 사용해서 배낭에 최대 가치를 담기
- 점화식은 물건을 넣었을 때 가치가 크다면 갱신
- dp[현재 무게] = 최대 가치
int w[100], p[100];
int dp[100001] = {0,};
for(int i = 0; i < n; i++) { // 물건 수
for(int j = k; j >= w[i]; j--) // 가치
dp[j] = max(dp[j], dp[j - w[i]] + p[i]);
}
for문 순서
- 2중 for문의 순서가 중요하다.
- 옳은 방법 → 조합을 위해서는 물건의 개수를 바깥 for문에 사용해야 한다.
- 하나의 물건씩 넣어본다고 생각하자.
- 틀린 방법 → 물건의 가치를 바깥 for문에 쓴다면 순열이 된다.
- 만약 하나의 가방에 여러 물건을 넣어보면 섞일 것이다.
역방향인 이유
가치를 정하는 for문을 정방향(inc)으로 한다면 똑같은 물건을 여러 번 중복 사용한 냅색이 된다.
역방향(dec)으로 한다면 물건을 단 한 번만 사용한 냅색이 된다.
만약 최대 무게가 6일 때, 3kg의 가치가 100원이라고 가정해 보자.
정방향의 경우, 3kg이 먼저 기록되면서 6kg이 3kg를 메모이제이션 해서 결과적으로 6kg에는 3kg가 2개 들어간다.
하지만 역방향이라면 가장 큰 6kg을 먼저 하기 때문에 3kg을 메모이제이션 할 배낭이 없다.
추천 문제