Untitled
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; }