백준 12865 평범한 배낭

algorithm : dp

 

해설

dp [i][j] 정의 : 1 ~ i번째 까지 물품을 사용해서 무게 j를 만들 때 물건들의 가치의 최댓값

 

예제

4 7

6 13

4 8

3 6

5 12

	1	2	3	4	5	6	7
13	0	0	0	0	0	13	0
8	0	0	0	8	0	13	0
6	0	0	6	8	0	13	14
12	0	0	6	8	12	13	14

dp배열에서 최댓값이 정답

 

dp[i][j]가 될 수 있는 경우는 item [i]를 사용하여 만들거나 사용 안 하는 경우 2가지가 있다

item을 사용해서 만들 때는 dp[i - 1][j - item [i]. first]를 만들 수 있는 경우에만 item을 사용하여 만들 수 있다

 

소스코드

#include<bits/stdc++.h>
#define LM 100000+10
#define INF 199999999
using LL = long long;
using namespace std;

int N,K;
int dp[100 + 10][LM];
pair<int,int> item[100 + 10];
int ans;

void input(){
    scanf("%d %d",&N,&K);
    for(int i = 1 ; i <= N ; i++)
        scanf("%d %d",&item[i].first,&item[i].second);
}

void DP(){
    for(int i = 1 ; i <= N ; i++){
        for(int j = 0 ; j <= K ; j++){
            if(0 <= j - item[i].first && (dp[i - 1][j - item[i].first] != 0 || j - item[i].first == 0))
                dp[i][j] = max({dp[i][j],dp[i - 1][j - item[i].first] + item[i].second});
            dp[i][j] = max(dp[i][j],dp[i - 1][j]);
            ans = max(ans,dp[i][j]);
        }
    }
    for(int i = 1 ; i <= N ; i++){
        for(int j  = 1 ; j <= K ; j++)
            printf("%d ",dp[i][j]);
        printf("\n");
    }
}

int main(){
    //freopen("input.txt","r",stdin);
    input();
    DP();
    printf("%d",ans);
    return 0;
}