समस्या विवरण
मान लीजिए एक शेफ है। और उसने अपने n व्यंजनों की संतुष्टि स्तर पर डेटा एकत्र किया है। शेफ किसी भी व्यंजन को 1 इकाई समय में पका सकता है। किसी व्यंजन का लाइक-टाइम गुणांक वास्तव में उस व्यंजन को पकाने में लगे समय सहित पिछले व्यंजनों को गुणा करके उसकी संतुष्टि स्तर होता है। यानी time[i] * satisfaction[i]।
हमें व्यंजन तैयार करने के बाद शेफ द्वारा प्राप्त लाइक-टाइम गुणांक का अधिकतम योग ज्ञात करना है। व्यंजन किसी भी क्रम में तैयार किए जा सकते हैं और शेफ इस अधिकतम मान को प्राप्त करने के लिए कुछ व्यंजनों को छोड़ सकता है।
उदाहरण
यदि इनपुट है: [-1,-7,0,6,-7], तो आउटपुट होगा 17, क्योंकि दूसरा और अंतिम व्यंजन हटाने के बाद, अधिकतम कुल लाइक-टाइम गुणांक होगा -1*1 + 0*2 + 6*3 = 17।
हल करने का दृष्टिकोण
इस समस्या को हल करने के लिए निम्नलिखित चरणों का पालन करें (DP + मेमोइजेशन):
- आकार 505 x 505 की एक सरणी dp परिभाषित करें
- solve() नामक एक फ़ंक्शन परिभाषित करें, जो idx, time, एक सरणी v लेता है:
- यदि idx, v के आकार के समान है, तो 0 लौटाएं
- यदि dp[idx][time] != -1, तो dp[idx][time] लौटाएं
- ret := -inf
- ret := solve(idx + 1, time, v) और v[idx] * time + solve(idx + 1, time + 1, v) का अधिकतम
- dp[idx][time] := ret
- ret लौटाएं
- मुख्य विधि से:
- dp को -1 से भरें
- सरणी v को सॉर्ट करें
- solve(0, 1, v) लौटाएं
C++ कार्यान्वयन
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int dp[505][505];
int solve(int idx, int time, vector<int>& v) {
if(idx == v.size()) return 0;
if(dp[idx][time] != -1) return dp[idx][time];
int ret = INT_MIN;
ret = max(solve(idx + 1, time, v), v[idx] * time + solve(idx + 1, time + 1, v));
return dp[idx][time] = ret;
}
int maxSatisfaction(vector<int>& v) {
memset(dp, -1, sizeof(dp));
sort(v.begin(), v.end());
return solve(0, 1, v);
}
};
int main() {
Solution ob;
vector<int> v = {-1,-7,0,6,-7};
cout << (ob.maxSatisfaction(v));
return 0;
}
इनपुट
{-1,-7,0,6,-7}
आउटपुट
17
