📌 알고리즘 - 백준 23061번 백남이의 여행 준비 문제풀이

문제

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

문제풀이

문제를 요약하면, $K_i$ 무게만큼의 담을 수 있는 가방이 $M$개 있을 때 $\frac{\text{가방에 담긴 물건의 가치의 합}}{\text{가방이 견딜 수 있는 최대 무게}}$이 가장 큰 가방 번호를 구하는 것이다.

단순 배낭 문제에서 배낭 개수가 1개에서 $M$개로 변했다. 하지만 생각없이 배낭 개수가 늘었다고 반복문을 추가해 $O(MNW)$에 구하면 시간 초과이다.

배낭 문제 DP식 정의를 생각하면 배낭의 무게한도를 가장 큰 배낭의 무게한도로 설정하면 다른 배낭들의 답이 $O(NW)$에 구한 DP배열에 모두 포함되는 것을 알 수 있다.

코드

#include <bits/stdc++.h>
#define endl '\n'
#define NMAX 110
#define MMAX 110
#define KMAX 1000010
#define ll long long

using namespace std;

int N, M;
int W[NMAX];
int V[NMAX];
int K[MMAX];
int dp[NMAX][KMAX];
int ans;
pair<ll, ll> tmp1;
pair<ll, ll> tmp2;

void Initialization() {
    memset(W, 0, sizeof(W));
    memset(V, 0, sizeof(V));
    memset(K, 0, sizeof(K));
    memset(dp, 0, sizeof(dp));
    ans = 1;
}

void Input() {
    cin>>N>>M;
    for (int i = 1; i <= N; i++) {
        cin>>W[i]>>V[i];
    }
    for (int i = 1; i <= M; i++) {
        cin>>K[i];
    }   
}

void Solution() {
    int maxK = 0;
    for (int k = 1; k <= M; k++) {
        maxK = max(maxK, K[k]);
    }
    for (int i = 1; i <= N; i++) {
        for (int w = 0; w <= maxK; w++) {
            if (w - W[i] >= 0) {
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-W[i]] + V[i]);
            } else {
                dp[i][w] = dp[i-1][w];
            }
        }
    }
    for (int i = 2; i <= M; i++) {
        tmp1 = make_pair(K[ans], dp[N][K[ans]]);
        tmp2 = make_pair(K[i], dp[N][K[i]]);
        if (tmp1.second * tmp2.first < tmp1.first * tmp2.second) {
			ans = i;
		}
    }
    cout<<ans;
}

void Solve() {
    Initialization();
    Input();
    Solution();
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    Solve();

    return 0;
}