[boj][c++] 12865 평범한배낭

12865 평범한 배낭

배낭문제라는 문제유형을 알아야 한다. 배낭의 용적 가능 무게가 k일 때 n개의 물건(각 물건에는 w:무게, v:가치가 존재함)이 존재한다면 배낭에 담을 수 있는 물건의 최대 가치는 몇인지 구하는 문제이다.

dp를 사용하지만 처음 접하는 문제이기 때문에 풀이를 자세하게 적어보려고 한다. 문제의 예제로 설명해보겠다.

w	v
6	13
4	8
3	6
5	12

이런 표가 있을 때 최대 가치를 구하기 위해서 배낭에 수납할 수 있는 무게가 1부터 k일 때의 모든 최대가치를 구하려고 한다.

물건번호(i) \ 최대무게(k)	k=1	k=2	k=3	k=4	k=5	k=6	k=7
i=1	0
i=2	0
i=3	0
i=4	0

배낭 최대 무게가 1일 때 모든 물건의 무게는 1을 넘으므로 모든 경우 가치는 0이다.

물건번호(i) \ 최대무게(k)	k=1	k=2	k=3	k=4	k=5	k=6	k=7
i=1	0	0
i=2	0	0
i=3	0	0
i=4	0	0

배낭 최대 무게가 2일 때 모든 물건의 무게는 2를 넘으므로 모든 경우 가치는 0이다.

물건번호(i) \ 최대무게(k)	k=1	k=2	k=3	k=4	k=5	k=6	k=7
i=1	0	0	0
i=2	0	0	0
i=3	0	0	6
i=4	0	0

배낭 최대 무게가 3일 때 i[3]의 무게가 3이므로 i[3]을 배낭에 넣었을 때 가치는 6이다.

물건번호(i) \ 최대무게(k)	k=1	k=2	k=3	k=4	k=5	k=6	k=7
i=1	0	0	0
i=2	0	0	0
i=3	0	0	6
i=4	0	0	6

배낭 최대 무게가 3일 때 i[4]의 무게는 5이라서 배낭에 넣을 수 없지만 바로 위에서 i[3]의 무게가 6이었으므로 여기까지 왔을 때 최대 가치는 dp[k][3-1]인 6이다.

물건번호(i) \ 최대무게(k)	k=1	k=2	k=3	k=4	k=5	k=6	k=7
i=1	0	0	0	0
i=2	0	0	0	8
i=3	0	0	6
i=4	0	0	6

배낭 최대 무게가 4일 때 i[2]의 무게는 4이므로 i[2]를 배낭에 넣었을 때 가치는 8이다.

물건번호(i) \ 최대무게(k)	k=1	k=2	k=3	k=4	k=5	k=6	k=7
i=1	0	0	0	0
i=2	0	0	0	8
i=3	0	0	6	8
i=4	0	0	6

배낭 최대 무게가 4일 때 i[3]의 무게는 3이므로 i[3]을 배낭에 넣었을 때 가치는 6이다. 그러나 위에서 i[2]를 배낭에 넣었을 때 가치가 8이었다. max(dp[i-1][k],v[i]) 연산을 통해 더 가치가 큰 값을 넣을 수 있다.

물건번호(i) \ 최대무게(k)	k=1	k=2	k=3	k=4	k=5	k=6	k=7
i=1	0	0	0	0
i=2	0	0	0	8
i=3	0	0	6	8
i=4	0	0	6	8

배낭 최대 무게가 4일 때 i[4]의 무게는 5이므로 i[4]를 배낭에 넣을 수 없지만 dp[3][4]의 무게가 8이었으므로 여기까지의 최대 가치는 8임을 알 수 있다.

물건번호(i) \ 최대무게(k)	k=1	k=2	k=3	k=4	k=5	k=6	k=7
i=1	0	0	0	0	0
i=2	0	0	0	8	8
i=3	0	0	6	8	8
i=4	0	0	6	8	12

배낭 최대 무게가 5일 때 i[4]의 무게는 5이므로 배낭에 넣을 수 있고 이때 가치는 12이다.

물건번호(i) \ 최대무게(k)	k=1	k=2	k=3	k=4	k=5	k=6	k=7
i=1	0	0	0	0	0	13
i=2	0	0	0	8	8	13
i=3	0	0	6	8	8	13
i=4	0	0	6	8	12	13

배낭 최대 무게가 6일 때 i[1]의 무게는 6이므로 배낭에 넣을 수 있고 이때 최대 가치는 13이다.

물건번호(i) \ 최대무게(k)	k=1	k=2	k=3	k=4	k=5	k=6	k=7
i=1	0	0	0	0	0	13	13
i=2	0	0	0	8	8	13	8
i=3	0	0	6	8	8	13
i=4	0	0	6	8	12	13

배낭 최대 무게가 7일 때 i[2]의 무게는 4이므로 배낭에 넣을 수 있고 이때 가치는 8이다.

그런데 여기서부터 고려할 것이 늘어난다. 최대 무게가 7이므로 무게가 4인 물건을 넣으면 3의 무게가 남는다. 무게가 3인 물건이 있으므로 물건을 여러개 넣을 수 있는 것이다.

또한 위에서 표를 채워넣은 것처럼 dp[2-1][7]의 가치가 더 크다면 이 값을 표에 채워야 한다. 이것을 점화식으로 나타내면 아래와 같다.

dp[i][k] = max(dp[i - 1][k], dp[i - 1][k - w[i]] + v[i])

max함수의 첫번째 인자는 직전 물건을 수납했을 경우, 두번째 인자는 현재 물건을 수납하고 남은 무게의 다른 물건을 수납했을 경우라고 볼 수 있다.

두번째 인자에서 dp[i-1][k-w[i]]+v[i]라는 식이 나온 이유는 k가 최대 무게를 의미하므로 현재 물건의 무게를 뺀 남은 무게의 물건과 현재 물건을 더하기 위해서이다. ㅎㅎ;; 직접 풀어보면 이해가 더 쉽다.

물건번호(i) \ 최대무게(k)	k=1	k=2	k=3	k=4	k=5	k=6	k=7
i=1	0	0	0	0	0	13	13
i=2	0	0	0	8	8	13	14
i=3	0	0	6	8	8	13	14
i=4	0	0	6	8	12	13	14

위의 내용대로 풀어보면 다음과 같은 식을 세울 수 있다.

dp[2][7]=dp[1][7]
혹은
dp[2][7]=dp[1][7-4]+v[4]

전자의 값은 13이고 후자의 값은 14이므로 후자의 가치가 더 크다. 따라서 dp[2][7]=14가 된다.

모든 표를 다 채웠다면 답도 나왔다. 가장 가치가 높은 것은 dp[n][k]라고 볼 수 있다. 즉 이 예제의 답은 dp[4][7]이다.

#include    <iostream>
#include    <algorithm>
using namespace std;

int n,k;
int w[101];
int v[101];
int dp[101][100001];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i]>>v[i];
    }
    for(int i=1;i<=k;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(w[j]<=i)
                dp[j][i]=max(dp[j-1][i],dp[j-1][i-w[j]]+v[j]);
            else
                dp[j][i]=dp[j-1][i];
        }
    }
    cout<<dp[n][k];
}

이건 물건을 쪼갤 수 없을 때 풀 수 있는 방법이고 물건을 쪼갤 수 있을 때는 접근하는 방식이 다르다고 한다.

미래의 나야 힘내 할수있ㅇ ㅓ!!