[백준 12865] 알고리즘 53일차 : 평범한 배낭

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

12865번: 평범한 배낭

동적계획법 C++

2020 하계 방학 알고리즘 스터디의 마지막을 장식할 DP 문제 knapsack 문제다!!!

문제는 설명하기 입아프니 위 사진을 참고하도록 하시고

이번 여름방학 스터디 마지막 문제로 knapsack 문제를 정석으로 코드를 짜보려고

이 문제를 골랐다.

 

접근방법

상향식 접근, 최적의 원리 등의 접근으로 풀이하는 대표적인 DP문제 중 하나인 knapsack(배낭채우기 0-1)문제

0-1이 아니면 그리디로 풀이하면 되지만 0-1은 DP로 풀이해야한다.

하지만 knapsack을 DP로 풀이한 아래 풀이법은 시간복잡도가 O(NW)이다.

배낭에 담을 수 있는 무게가 너무 커지면 이것도 N^2이상의 복잡도를 갖는다. (NP문제)

 

갖고있는 물건의 개수 만큼의 행을 갖고, 배낭에 담을 수 있는 무게의 범위 만큼의 열을 갖는 이차원 배열을 사용한다.

배열에 저장되는 값은 이렇다. (행 : i, 열 : w) i까지의 물건을 w무게 만큼 넣을 수 있다고 할때 가장 큰 가치를 저장한다.

이때 i번째 물건을 넣지 않았을 때와 i번째 물건을 넣을 공간을 마련한 후 i번째 물건을 넣었을 때의 배낭에 든 물건의 가치를 비교한다.

이때 추가로 처리하는 것은 w무게 보다 i번째 물건의 무게가 클때 이때는 i번째 물건을 넣지 않았을 때의 경우와 같은 값을 저장한다.

 

소스코드

#include <iostream>
using namespace std;

int dp[101][100001];
int main(){

    int n, k;
    cin >> n >> k;

    int weight, worth;
    for(int i = 1 ; i <= n ; i++){
        cin >> weight >> worth;
        for(int w = 0 ; w <= k ; w++){
            if(weight > w || (worth+dp[i-1][w-weight] < dp[i-1][w]) )
                dp[i][w] = dp[i-1][w];
            else
                dp[i][w] = dp[i-1][w-weight] + worth;
        }
    }
    
    cout << dp[n][k];
    return 0;
}