[알고리즘] 백준 12865 c++

김민주·2023년 5월 16일
0
post-thumbnail

평범한 배낭

문제 링크

12865번: 평범한 배낭

틀린이유

  • dp인 거까지는 찾았지만 dp에 확신이 없었다
  • dp의 테이블을 정의해놓고 안되자 다른 테이블을 정의하려하지 않고 모르겠다 시전 (dp에 확신이 없었기 때문임)
💡 유형에 확신을 갖고 문제풀이 접근하자. 안되면 다른 식을 찾아봐야지 (ex. 1차원 안되면 2차원으로)

문제 분석

문제

  • N개의 물건 (각 물건은 무게 w와 가치 v를 가짐)
  • 배낭에는 최대 K만큼의 무게만 넣을 수 있음
  • 배낭에 넣을 수 있는 물건의 가치의 최댓값은?

입력

  • 1 ≤ N ≤ 100
  • 1 ≤ K ≤ 100,000
  • 1 ≤ w ≤ 100,000
  • 0 ≤ v ≤ 1,000

해결방안

조합으로 백트래킹하기에는 N이 크다 (백트래킹은 N ≤ 15 정도가 적당)

그리디로 하기에는 무게 또는 가치를 기준으로 해야하므로 맞지 않는다 (반례 생김)

그렇다면 DP인 것 같은데… 아니 DP다. 확신을 갖고 테이블 정의하자.

1. 테이블 정의

d[i] = 무게가 i일 때 가치합

위와 같이 테이블을 정의했을 때 물건을 넣었는지 안넣었는지 유무를 확인할 수가 없다. 2차원 배열로 선언해보자. 그럼 column을 물건 번호로 두고, row를 무게로 두면 되겠다..!

d[i][j] = i 번째 물건을 담을 차례, 무게가 j일 때 가치합

2. 점화식 찾기

column은 0~N까지, row는 0~K까지로 두고 예제 1에서 점화식을 찾아보자.

N = 4, K = 7
{{6, 13}, {4, 8}, {3, 6}, {5, 12}} // 각 물건의 무게와 가치를 담은 배열

w[i] ≤ k 일 때 배낭에 물건을 넣을 수 있다.

1) 물건을 넣을 수 있는 경우

i = 2, 무게가 4인 물건을 넣으려고 한다.

4 ≤ k 여야하므로 d[2][4]와 d[2][5] = 8로 채워졌다. d[2][6]과 d[2][7]에서는 최댓값 확인하는 작업이 필요하다. 왜냐하면 이미 무게가 꽉 채워진 것이므로 두 물건을 가져갈 수는 없다. 둘 중 하나만 가능하다.

01234567(K)
0
11313
288
3
4 (N)

현재 물건을 선택했을 때와 현재 물건을 선택 안했을 때 두 경우가 있다.

현재 물건을 선택했을 때 : d[1]6-w[2]]+v[2]

현재 물건을 선택안했을 때 : d[1][6]

즉, max(d[i-1]k-w[i]] + v[i], d[i-1][k])를 하면 되겠다.

2) 물건을 넣을 수 없는 경우

물건을 넣을 수 없는 경우는 빈칸으로 남겨놔야할까? 아니다. d[i-1][k] 값을 그대로 가져오면 된다. 현재 물건을 선택 안했을 때와 똑같기 때문이다.

이제 점화식이 완성되었다.

if (w[i] <= j) 
	d[i][j] = max(d[i-1][j-w[i]] + v[i], d[i-1][j]);
else 
	d[i][j] = d[i-1][j];

3. 초기값 찾기

배열 d의 초기값을 전부 0으로 하고, i와 j 모두 1부터 시작하면 된다.

4. 구하는 값

구하는 값은 N번까지 물건을 넣을지 말지 선택했고, 무게가 K일 때를 확인해보면 되겠네요. 즉, d[N][K]가 되겠죠?

전체 코드

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

int N, K;
int d[102][100002];
int w[102];
int v[102];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> K; 
    for (int i=1; i<=N; i++){
        cin >> w[i];
        cin >> v[i];
    }

    for (int i=1; i<=N; i++){
        for (int j=1; j<=K; j++){
            if (w[i] <= j) { // 담을 수 있음 (선택 가능)
                d[i][j] = max(d[i-1][j], d[i-1][j-w[i]] + v[i]);
            } else { // 담을 수 없음
                d[i][j] = d[i-1][j];
            }
        }
    }
    cout << d[N][K];

    return 0;
}
profile
즐거운 개발자 김민주입니다🙂

0개의 댓글