[백준 12865번] 평범한 배낭

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

12865번: 평범한 배낭

풀이)

4 7
6 13
4 8
3 6
5 12

위와 같은 입력이 있을 때, 물건이 배낭에 담기지 않는다는 것을 해당 dp 초기값으로 설정(직전의 갯수 최대 가치)을 해두고, 담긴다면 직전에 방금 초기로 설정해두었던 값(직전의 갯수 최대가치)와 총 중량에서 내가 담을 무게만큼을 뺏을때의 값(dp[i-1][j-w[i])에서 담을 무게만큼 넣은 값 중 더 큰 값을 해당 dp값으로 설정하면 된다. 이런식으로 1개 ~ N개까지 1부터 K까지 담을 수 있는 최대 값을 dp로 쭉 채워서 맨 마지막에 해당하는 값인 dp[N][K]가 정답이 된다.

#include <iostream>
using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int N, K;
    int w[101], v[101], dp[101][100001]; 
    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] >= 0)
                dp[i][j] = max(dp[i][j] , dp[i - 1][j - w[i]] + v[i]);
        }
    }
    cout << dp[N][K];
    return (0);
}

 

 

제 코드는 절대 완벽하지 않습니다

더 좋은 풀이방법 혹은 코드에 관한 질문이 있으시면 언제든 댓글주세요!