nord vpnnord vpn
Ad

Untitled

mail@pastecode.io avatar
unknown
c_cpp
a month ago
1.3 kB
3
Indexable
Never
#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

unordered_map<pair<int, int>, int> dp;

int dfs(int i, int remaining_bandwidth, const vector<int>& bandwidth, const vector<int>& request) {
    if (i == bandwidth.size()) {
        return 0;
    }

    pair<int, int> state = make_pair(i, remaining_bandwidth);
    if (dp.find(state) != dp.end()) {
        return dp[state];
    }

    if (bandwidth[i] > remaining_bandwidth) {
        dp[state] = dfs(i + 1, remaining_bandwidth, bandwidth, request);
        return dp[state];
    } else {
        dp[state] = max(dfs(i + 1, remaining_bandwidth, bandwidth, request),
                       dfs(i + 1, remaining_bandwidth - bandwidth[i], bandwidth, request) + request[i]);
        return dp[state];
    }
}

int max_requests(int total_bandwidth, const vector<int>& bandwidth, const vector<int>& request) {
    return dfs(0, total_bandwidth, bandwidth, request);
}

int main() {
    int total_bandwidth = 500;
    vector<int> bandwidth = {200, 100, 350, 50, 100};
    vector<int> request = {270, 142, 450, 124, 189};

    int result = max_requests(total_bandwidth, bandwidth, request);
    cout << "Total number of requests that can be served: " << result << endl;

    return 0;
}

nord vpnnord vpn
Ad