Post

baekjoon 12865:평범한 배낭

baekjoon 12865 평범한 배낭

12865번 평범한 배낭

접근

쪼갤 수 없는 평범한 배낭은 dp 문제이다.
dp(i, j) = i번째부터 n번째까지 물건을 이용해서 j의 용량을 가지고 있는 가방을 싸는 최대 가치 i번째 물건을 넣는지 말지에 따라서 계속 뒤로 i+1 i+2따지면서 max하면됨.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <vector>
#include <array>
using namespace std;
array<array<int, 100001>, 101> cache{};
int dp(int i, int w, vector<array<int, 2>>& v); //i~n까지 중에 w공간에 최대 가치
int main(){
  int n, k; cin >> n >> k;
  vector<array<int, 2>> v(n);
  for(int i = 0; i < n; i++){
    cin >> v[i][0] >> v[i][1];
  }
  for(auto& i:cache){
    for(auto& j:i){
      j = -1;
    }
  }
  //init
  cout << dp(1, k, v);
  
  
  
  

  return 0;
}
int dp(int i, int w, vector<array<int, 2>>& v){
  if(i == v.size()+1){
    return 0;
  }
  if(w == 0){
    return 0;
  }
  int& ret = cache[i][w];
  if(ret != -1){
    return ret;
  }
  ret = 0;
  for(int j = i; j <= v.size(); j++){
    if(w-v[j-1][0] >= 0){
      ret = max(ret, dp(j+1, w-v[j-1][0], v)+v[j-1][1]);
    }
  }
  
  return ret;
  
  
}

배운 점

dp

This post is licensed under CC BY 4.0 by the author.