[12920] 평범한 배낭 2

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

12920번: 평범한 배낭 2

<문제>

냅색문제는 물건의 개수가 1개 혹은 무한대일때에는 쉽게(?) 풀린다. 어쨋든 웰노운이니까..

그런데 물건의 개수가 2개, 3개같이 애매한 숫자라면 의외로 어려워진다.

물론 2개라면 물건의 개수만 2배로 넣어주면 되지만, 이 문제는 물건의 개수를 하나씩 분할해서는 풀 수 없다.(TLE)

그렇기에 이 문제의 일반적 해법은 2진수꼴로 물건을 분할하는, 비트마스킹같은 테크닉이 들어간 DP문제라 할 수 있다.

 

사실 이문제를 풀때에는 비트마스킹도 몰랐고, 

count배열을 만들어서 물건의 개수를 계속 업데이트해가면 되겠다!라는 생각을 하고 접근했던거 같은데,

정작 구현하는게 매우 어려웠던 것 같다.

<소스코드>

#include<stdio.h>
#include<algorithm>
using namespace std;
int dp[100001];
int w[101], c[101], k[10001][101];//무게,가치,개수
int main(void) {
    int i, j,p, n, m, max = 0;
    scanf("%d %d", &n, &m);
    for (i = 0; i < n; i++) {
        scanf("%d %d %d", &w[i], &c[i], &k[0][i]);
        for (j = 1; j <= m; j++) {
            k[j][i] = k[0][i];
        }
    }
    for (i = 0; i <= m; i++) {
        dp[i] = 0;
        for (j = 0; j < n; j++) {
            if (i - w[j] >= 0) {
                if (dp[i] < dp[i - w[j]] + c[j] && k[i - w[j]][j] != 0) {
                    dp[i] = dp[i - w[j]] + c[j];
                    for (p = 0; p < n; p++) {
                        k[i][p] = k[i - w[j]][p];
                    } 
                    k[i][j]--;
                }
            }
        }
    }
    for (i = 1; i <= m; i++) {
        if (max < dp[i])
            max = dp[i];
    }
    printf("%d", max);
    return 0;
}

 

예전에 작성해본 코드지만, 지금봐도 이해가 잘 안된다.

덱을 이용한 최적화 기법이나 비트마스킹 DP를 쭉 풀때 다시보면 좋은 문제이긴 싶다.