[백준 알고리즘/C++] 12865 평범한 배낭

 

 

무게 W와 가치 V를 가지는 물건 N개가 있다

K만큼의 무게만 들 수 있을 때, 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 구하는 문제

 

 

가치 기준으로만 계산하거나 무게 기준으로만 계산하면 오답이 나옴

무게도 누적시키고, 가치도 누적시켜 줘야한다..

dp로 고려해야 하는 게 두 가지 이상이므로 2차원 배열을 써준다

 

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int n, k;
int w[101], v[101];
int dp[101][100001];
int ans = 0;
 
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    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++) {
            if (w[i] <= j)
                dp[i][j] = max(dp[i - 1][j], v[i] + dp[i - 1][j - w[i]]);
            else
                dp[i][j] = dp[i - 1][j];
 
            ans = max(ans, dp[i][j]);
        }
    }
 
    cout << ans;
}