백준 12865: 평범한 배낭

문제 링크 : https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 문제 설명 

 

엄처 유명한 배낭 문제(Knapsack Problem 이다 .. 

참고 : https://ko.wikipedia.org/wiki/%EB%B0%B0%EB%82%AD_%EB%AC%B8%EC%A0%9C

 

 알고리즘 

 

DP 알고리즘을 이용하여 간단하게 풀 수있다.

예제 DP 배열 진행 단계

 

 코드 

 

#include<iostream>
#include<algorithm>
 
using namespace std;
 
 
int main() {
 
    cin.tie(NULL);
    ios::sync_with_stdio(false);
 
    int dp[101][100001];
    int w[101], v[101];
    int N, K;
 
    cin >> N >> K;
 
 
 
    for (int i = 1; i <= N; i++)
        cin >> w[i] >> v[i];
 
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= K; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= w[i]) {
                dp[i][j] = max(dp[i][j], dp[i-1][j - w[i]] + v[i]);
            }
 
        }
 
    }
 
    cout << dp[N][K];
}