12865-평범한 배낭

12865-평범한 배낭

 

전형적인 Knapsack문제이다. 각 물품마다 무게와 가중치가 주어지고 정해진 무게 안에서 가중치의 합이 최대가 되도록 만들면 된다.

dp테이블의 의미는 

dp[a][b]=c : a번째 물품까지 봤을 때, b이하의 무게로 만들 수 있는 최대 가중치의 합=c

이다. 물품은 모두 1개씩 밖에 존재하지 않기 때문에 2차원 dp로 디자인 해야 하는 것 같다.

문제의 디스크립션은 조금 다르지만 동전시리즈 문제랑 비슷한 느낌이다. 현재 i번재 물품까지 보고 있을 때, 현재 무게(b)로 최대의 가중치를 구하기 위해서는 기존의 (i-1)번째 까지의 물품으로 만들 수 있는 가중치의 합과 이번에 i번째 물품을 이용해서 새롭게 만들어 낼 수 있는 가중치의 합 중에서 큰 값을 dp배열에 저장하면 된다.

처음 풀 때는 물품을 무게를 기준으로 오름차순으로 정렬해서 풀었는데, 정렬을 안해도 Accept을 받았다. 이 문제는 왠지 정렬을 해야 할 것 같은 느낌이 들었는데...솔직히 아직 언제 정렬을 해야 하는지 이해하지 못한 것 같다.

그리고 1차원 dp배열로도 풀 수 있는 것 같은데 풀이가 와닿지 않아서 나는 그냥 2차원으로 했다.

 

int dp[109][100009]={0};
int main(){
    int n,k;    scanf("%d %d",&n,&k);
    
    for(int i=1 ; i<=n ; i++){
        int w,v;    scanf("%d %d",&w,&v);
        for(int j=1 ; j<=k ; j++){
            if(j >= w) dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v);
            else dp[i][j] = dp[i-1][j];
        }
    }
    
    printf("%d\n",dp[n][k]);
    
	return 0;
}