(12865) 평범한 배낭

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

단계별로 풀어보기

21단계(동적 계획법 1) 16번째

 

 

 

DP 알고리즘 문제로 유명한 배낭 문제의 일종

dp[a][b]를 a번째 물건까지 넣을 수 있고 배낭의 최대 무게가 b일 때 가치의 최대값이라고 하자.

기본적으로 dp[a][b]는 a-1번째 물건까지 넣었을 때 최대값인 dp[a-1][b]이다.

만약 a번째 물건을 넣으려면 b≥w이고, 이때의 가치는 dp[a-1][b-w]+v가 된다.

1부터 n까지 모든 a에 대해 1부터 k까지 모든 b값을 탐색하며 b의 범위에 따라 첫 번째 값, 또는 두 값 중 큰 값을 저장하면 된다.

 

 

 

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

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

 

 

 

이 문제도 dp[i]줄을 구할 때 필요한 값은 dp[i-1]줄밖에 없으므로 메모리를 절약할 수 있다.

기본적으로 dp[i][j]= dp[i-1][j]이므로 dp를 한 줄만 쓴다면 이 부분을 갱신할 필요가 없고,

a번째 물건을 넣는 경우를 계산할 때 j를 k부터 거꾸로 탐색하는 이유는 물건을 두 번 넣는 것으로 계산하지 않기 위함이다.

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

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