[C++] 12865번 평범한 배낭 - DP, 배낭 문제

#include <iostream>
#include <vector>
#include <algorithm>

#define MAX_NUM 101
#define MAX_WEIGHT 100001

using namespace std;

//물품의 수 N, 준서가 버틸 수 있는 무게 K, 물건의 무게 W, 물건의 가치 V
int N, K, W, V;
int map[MAX_NUM][MAX_WEIGHT];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> K;
    
    for(int i=1; i<=N; i++) {
        cin >> W >> V;
        for(int j=1; j<=K; j++) {
            if(W<=j)
                map[i][j]=max(map[i-1][j-W]+V, map[i-1][j]);
            else
                map[i][j]=map[i-1][j];
        }
    }
    cout << map[N][K];
    
    return 0;
}

 

하루에 4개 풀었더니 지친다.... 배낭 문제는 또 새로운 알고리즘인가 했는데 그냥 DP랑 같은 것 같다.

 

 

 

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.