C++

DP

재귀함수

#include <cstdio>

#include <algorithm>

#include <climits>

#include <cstring>

using namespace std;

int N,W;

int dt[110][10010];

int we[110],vv[110];

int serch(int n, int w){

    if(n==N){

        return 0;

    }

 

    if(dt[n][w]!=-1){

        return dt[n][w];

    }

 

    if(w+we[n]>W){

        return dt[n][w] = serch(n+1,w);

    }

 

    return dt[n][w] = max(serch(n+1,w+we[n])+vv[n],serch(n+1,w));

}

int main()

{

    memset(dt,-1,sizeof(dt));

    scanf("%d %d",&N,&W);

    for(int i=0;i<N;i++){

        scanf("%d %d",&we[i],&vv[i]);

    }

    printf("%d",serch(0,0));

    return 0;

}

Bottom up

#include <cstdio>

#include <algorithm>

#include <climits>

#include <cstring>

using namespace std;

int N,W;

int dt[110][10010];

int we[110],vv[110];

 

int main()

{

    scanf("%d %d",&N,&W);

    for(int i=1;i<=N;i++){

        scanf("%d %d",&we[i],&vv[i]);

    }

 

    for(int i=1;i<=N;i++){

        for(int w=0;w<=W;w++){

            dt[i][w] = dt[i-1][w];

            if(w - we[i] >= 0)

                dt[i][w] = max(dt[i][w], dt[i-1][w - we[i]] + vv[i]);

        }

    }

 

    int max_ = 0;

    for(int w=0;w<=W;w++){

        max_=max(max_,dt[N][w]);

    }

    printf("%d",max_);

    return 0;

}