BJ12865 평범한배낭

풀이

DP

1. 1번째부터 N번째까지 물품을 담을 때 담을 수 있는 최대 가치를 기록한다.
2. 담을 때 이전까지 담은 물품들의 무게합들의 경우의 수에 기록된 DP(해당 무게에서의 최대 가치)를 확인한다.
   1. DP 값에 현재 물품의 무게를 더한 값에 있는 가치와 비교해서 큰 값을 담는다.
3. DP에 있는 값 중에 가장 큰 값을 출력한다.

코드

//! 2020.03.17
// TODO BJ12865_평범한배낭
#include<cstdio>
#include<vector>
using namespace std;

const int MAX = 100050;
int N,K;
int DP[MAX];
pair <int,int> inData[105];

int getMax(int n1,int n2){
    if(n1>n2) return n1;
    else return n2;
}

int getResult(){
    for(int i=0;i<N;i++){
        int w = inData[i].first;
        int v = inData[i].second;
        for(int k=K;k>=0;k--){
            if(DP[k]!=-1){
                int nextW = k+w;
                int nextV = DP[k]+v;
                if(nextW<=K) DP[nextW] = getMax(DP[nextW],nextV);
            }
        }
    }
    int ret = 0;
    for(int i=0;i<=K;i++) ret = getMax(ret,DP[i]);
    return ret;
}

int main(){
    // freopen("input.txt","r",stdin);
    scanf("%d %d",&N,&K);
    for(int n=0;n<N;n++){
        int W,V;
        scanf("%d %d",&W,&V);
        inData[n] = make_pair(W,V);
    }

    for(int i=1;i<=K;i++) DP[i] = -1;
    DP[0] = 0;

    printf("%d\n",getResult());
    return 0;
}

실수

이전에 담은 경우의 수들을 기록한 DP를 확인할 때 1부터 확인하면서 더한 값을 다음 DP에 메모하는 식으로 구현했었다.

그렇게 하게 되면 다음 DP값이 현재 DP값에 덮이게되고 원래 확인하려던 값이 아닌 수정된 값들이 다시 수정되게 되었다.

그래서 for loop를 가장 큰 값에서부터 줄여가면서 확인하도록 만들어 그런 경우를 없애주었다.