[ BOJ 백준 12865번 - 평범한 배낭 ] 해설 및 코드

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

 

목적

배낭에 넣을 수 있는 물건들의 가치의 최댓값을 구하자.

 

접근법

1. s[i][j]는 i개의 물건들을, 최대 j의 무게까지 담을 수 있는 가방에 담을 때의 최대 가치로 정한다. 다음과 같은 입력으로 보자.

6 9
3 6
2 7
4 6
4 2
4 10
1 5

총 6개의 물건이 있고 가방에 담을 수 있는 최대 무게는 9이다. 먼저 무게가 3이고 가치가 6인 첫 번째 물건으로 s값을 갱신하면 다음과 같이 될 것이다. 

다음 무게가 2이고 가치가 7인 두 번째 물건으로 s값을 갱신해보자.

s[2][7]을 보면 s[2][7 - 2] + 7 과 s[1][7]중에 최대값으로 값을 채워 넣은 것을 알 수 있다.

즉, s[i][j] = max(s[i - 1][j], s[i][j - w] + v)이며, 이와 같은 방법으로 배열을 다 채우면 다음과 같이 될 것이다.

s의 크기가 100*100000까지는 필요 없으므로 갱신하는 순서를 뒤에서 앞으로 바꿔 최대값을 구하자.

#include<bits/stdc++.h>
using namespace std;
 
int s[(int)1e5 + 1]{};
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, k; cin >> n >> k;
    while (n--) {
        int w, v; cin >> w >> v;
        int i = k + 1;
        while (--i >= w)s[i] = max(s[i], s[i - w] + v);
    }
    cout << s[k];
    return 0;
}

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.