백준 12865 평범한 배낭

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

간단한 다이나믹 문제입니다.

memo[x][y]에는 1번부터 x번물건 중 일부를 배낭에 넣어 무게가 y(k 이하)인 상황에서 가질 수 있는 가장 큰 가치를 배열에 넣어줍니다.

이때 점화식은

\[( arr[n][i+arr[n].first]=\overset { i\quad \le \quad k-arr[n].first }{ \underset { i=0 }{ MIN } } (arr[n-1][i]+arr[n].second)\] \[arr[n][i]=\overset { i\quad \le \quad k }{ \underset { i=0 }{ MIN } } arr[n-1][i]\]

중 작은 값이 된다.

#include<bits/stdc++.h>
using namespace std;
int memo[105][100005]; // memoization
pair<int,int> arr[105];
int main(void){
  ios::sync_with_stdio(false); cin.tie(NULL);
  int n,k; cin>>n>>k;
  for(int i=1;i<=n;i++) cin>>arr[i].first>>arr[i].second;
  for(int i=1;i<=n;i++){
    for(int j=0;j<=k-arr[i].first;j++){
      memo[i][j+arr[i].first]=max(memo[i][j+arr[i].first],memo[i-1][j]+arr[i].second);
    }
    for(int j=0;j<=k;j++) memo[i][j]=max(memo[i][j],memo[i-1][j]);
  }
  int ans=0;
  for(int i=0;i<=k;i++) ans=max(ans,memo[n][i]);
  cout<<ans;
  return 0;
}