백준 12865 - 평범한 배낭

문제 : https://www.acmicpc.net/problem/12865

 

풀이과정

이 문제는 짐을 쪼갤 수 없는 0-1배낭 문제이다.

 

물품의 수 N(1 ≤ N ≤ 100)와 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 

두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

 

점화식으로 표현하면 아래와 같다.

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)

"i번째 순번까지 물건을 담았고 j만큼의 무게가 실렸을 때 최대 가치" 를 의미한다.

 

1. dp[i-1][j] : 배낭에 물건을 넣지 않는다는 의미이다.

i번째 물건을 넣지 않고, 그 이전 물건까지 넣은 j 무게에서 최댓값 을 저장한다.

2. dp[i-1][j-w] + v : 배낭에 물건을 넣을 수 있다.

dp[i][j] 에는 최대 가치 를 저장해야 하므로 이전 물건과 무게를 제외한 최댓값 + 현재 물건의 가치 를 저장한다.

 

3. 이중for문을 통해 각 물건의 순번마다, 배낭의 최댓값까지 탐색해본다.

// 1부터 N개까지
// 1부터 최대무게까지
for(int i=1; i<=N; i++) {
    for(int j=1; j<=K; j++) {
        ....
    }
}

무게 가치
6 13
4 8
3 6

 

3-1. 첫 번째 물건을 넣었을 때 dp[1][6] = 13이 될 것이다. (나머지는 0)

3-2. 두 번째 물건만 처음 넣었을 때 dp[2][4] = 8 이며, 이전 물건의 무게와 합할 수 없다. (나머지는 0)

3-3. 세 번째 물건만 처음 넣었을 때 dp[3][3] = 6 이며, 이전 물건의 무게와 합했을 때 dp[3][7] = dp[3-1][7-3] + 6 = 14가

된다.

 

코드

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

// 짐을 쪼갤 수 없는 0-1 배낭문제
typedef struct items {
    int w,v;
}it;

vector <it> bag;
// dp[순번][무게] = 해당 순번까지 진행된 무게에서의 최대가치
int dp[101][100001];
int N,K,W,V;

int main()
{
    scanf("%d %d",&N,&K);
    for(int i=0; i<N; i++) {
        scanf("%d %d",&W,&V);
        bag.push_back({W,V});
    }
    for(int i=1; i<=N; i++) {
        for(int j=1; j<=K; j++) {
            int v = bag[i-1].v;
            int w = bag[i-1].w;
            // 배낭에 넣을 수 있다면
            if(j-w >= 0) 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]);
}