백준 23061번 백남이의 여행 준비 [C++]

 

 

#문제 간단 정리

 

배낭 DP 문제

 

 

#문제 해결 방법

 

딱히 특별할 풀이랄게 없다 배낭문제인데

DP는 최대 배낭사이즈로 해주고 

각 배낭들의 효율성만 비교해주면된다.

 

1차원배열로 풀었지만 2차원 배열로 풀어도 딱히 메모리초과는 안날 것 같으니 쉬운 문제인 듯하다.

 

#전체 코드

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <cstring>

using namespace std;

typedef long long ll;
typedef long double ld;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);


    int n, m;
    cin >> n >> m;

    //무게,가치
    vector<pair<int, int>> items(n);

    for (int i = 0; i < n; i++) {
        cin >> items[i].first >> items[i].second;
    }

    vector<int> bags(m);
    int maxSize = 0;
    for (int i = 0; i < m; i++) {
        cin >> bags[i];
        maxSize = max(bags[i], maxSize);
    }

    vector<int> dp(maxSize + 1, 0);
    for (int i = 0; i < n; i++) {
        int w = items[i].first;
        int v = items[i].second;
        for (int W = maxSize; W >= w; W--) {
            dp[W] = max(dp[W], dp[W - w] + v);
        }
    }

    ld ans = -1;
    int ansIndex = 0;
    for (int i = 0; i < bags.size(); i++) {

        if ((ld)dp[bags[i]] / (ld)bags[i] > ans) {
            ansIndex = i;
            ans = (ld)dp[bags[i]] / (ld)bags[i];
        }
    }



    cout << ansIndex + 1 << '\n';

    return 0;
}