Boj 배낭 문제 총집합

왜 시험기간만 되면 알고리즘이 재밌어지는건지 모르겠다.

 

오늘은 냅색(dp) 문제를 몇개 풀었다. 잠깐만 풀려고 했는데 생각보다 아이디어를 생각해내는데에 오래 걸렸다.

 

Boj 9084 동전

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

Boj 2293 동전 1

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

Boj 17845 수강과목

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

Boj 7579 앱

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

 

 

동전의 경우에는 금방 풀었다. 동전의 종류가 모두 달랐고, 동전을 여러번 사용할 수 있었기에 이를 이용하여 특정 값을 만들 수 있는 가짓수를 구하는 것이므로, dp 배열은 i원을 이룰 수 있는 방법의 수로 정의한 후,

dp[j] = dp[j] + dp[j-cost[i]] 라는 간단한 점화식으로 풀렸다. i번째 동전을 반영하여 가짓수를 업데이트하는 것이 핵심.

또한 0원을 표현하는 방법은 1가지라는 것을 염두에 두어야 했다.

 

전체 코드

#include <stdio.h>

int coin[25];
int dp[10001];


int main(){
    int T;
    scanf("%d", &T);

    while(T--) {
        for(int i = 0; i<=20; i++) {
            coin[i] = 0;
        }
        for(int i = 0; i<=10000; i++) {
            dp[i] = 0;
        }
        int N, M;
        scanf("%d", &N);
        for(int i = 0; i < N; i++) {
            scanf("%d", &coin[i]);
        }
        scanf("%d", &M);

        dp[0] = 1;

        for(int i = 0; i < N; i++) {
            for(int j = coin[i]; j <= M; j++) {
                dp[j] = dp[j] + dp[j-coin[i]];
            }
        }
        printf("%d\n", dp[M]);
    }
}

 

동전1 또한 동전과 동일한 문제이므로 풀이 코드는 유사했다.

 

 

수강과목은 용량이 주어진 냅색 문제로 12865와 동일한 문제였지만 한번 더 풀이를 상기하는 의미에서 코드를 짜보았다.

전체코드.

 

#include<iostream>
using namespace std;

int I[1001];
int T[1001];
int dp[1001][10001];

int main() {

    int N, K;
    cin >> N >> K;
    for(int i = 1; i <= K; i++) {
       cin >> I[i] >> T[i];
    }
    for(int i = 1; i <= K; i++) {
        for(int j = 0; j <= N ; j++) {
            if(j < T[i]) {
                dp[i][j] = dp[i-1][j];
                continue;
            }
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-T[i]] + I[i]);
        }
    }
    cout << dp[K][N];


}

 

 

앱은 조금 어려웠다. 특히 앱을 한번만 끌 수 있다는 조건을 어떻게 활용할지 난감하였다. 

10000000까지 늘어나는 M의 범위 또한 헷갈리는 요소였다. 

하지만 이는 중복 반영을 방지하는 역배낭 (큰 인덱스부터 업데이트 하여 중복 반영을 없애는 방식) 을 사용하고, dp의 정의를 'i 만큼의 비용으로 가장 많이 확보할 수 있는 메모리의 양 '으로 정의하면 해결되는 문제였다.

 

정답은  for문을 돌려 가장 먼저 M 이상의 값이 나타나는 dp배열의 인덱스를 출력하면된다.

비용이 모두 0일 경우는 정답이 0이 될 수 있기 때문에 1base로 코드를 짰더라도 for문을 0부터 시작해야 한다는 것이 함정.

 

전체 코드

#include <iostream>
using namespace std;

int mem[101];
int val[101];
int dp[10001]; //i 만큼의 가치로 확보할 수 있는 최대 메모리 수

int main() {

    int N, M;
    cin >> N >> M;
    for(int i = 0; i < N; ++i) {
        cin >> mem[i];
    }
    for(int i = 0; i < N; ++i) {
        cin >> val[i];
    }
    for(int i = 0; i < N; ++i) {
        for(int j = 10000; j >= val[i]; --j) {
            dp[j] = max(dp[j], dp[j-val[i]] + mem[i]);
        }
    }

    for(int i = 0; i <= 10000; ++i) {
        if(dp[i] >= M) {
            cout << i;
            break;
        }
    }
    return 0;
}