[12865] 평범한 배낭

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

<문제>

냅색은 3종류가 있다.

1) 물건의 개수가 무한대인 경우 -> DP로 해결한다. 가장 일반적인 형태인듯 싶다.

2) 물건의 개수가 1개인 경우 -> DP로 해결한다. 1번과는 다르지만, 사실 코드는 매우 유사하다.

3) 물건을 쪼갤 수 있는 경우 -> Greedy로 해결한다. 매우 직관적인 Greedy라 1,2번에 비해서 쉽다.

 

이번문제는 2번에 해당되고, 1번과의 차이점은 '역방향'에 있다.

왜 역방향으로 DP를 갱신해야 할까?

DP를 왼쪽부터(정방향) 갱신하게 되면, 이미 해당 물건을 넣어서 갱신한 DP를 다시 참조하게 되어
물건이 중복으로 선택된다.

반대로, 오른쪽부터(역방향) 돌리게되면 모든 물건은 최대 1번만 선택되는 제약조건을 아주쉽게 커버할 수 있다.

 

<소스코드>

#include<stdio.h>
int w[101],v[101],dp[100001];
int main(void) {
    int i, j, n, k;
    scanf("%d %d", &n, &k);
    for (i = 0; i < n; i++)
        scanf("%d %d", &w[i], &v[i]);
    for (i = 0; i < n; i++)
        for (j = k; j >=w[i]; j--)
            if (dp[j] < dp[j - w[i]] + v[i])
                dp[j] = dp[j - w[i]] + v[i];
    printf("%d", dp[k]);
    return 0;
}

물건의 개수가 무한대라면 9라인의 for를 정방향으로 바꾸면 된다.