मान लीजिए कि हमारे पास संख्याओं की एक सूची है जिसे जॉब कहा जाता है और दूसरा मान k है। अब हम सभी कार्यों को k अलग-अलग दिनों में समाप्त करना चाहते हैं। कार्यों को दिए गए क्रम में किया जाना चाहिए और प्रत्येक दिन में हमें एक कार्य पूरा करना होगा। नौकरी की कठिनाई मैं नौकरियों में संग्रहीत है [i] और एक दिन में नौकरियों की सूची को पूरा करने की कठिनाई उस दिन की जाने वाली अधिकतम कठिनाई होगी। इसलिए हमें k अलग-अलग दिनों में कार्य करने में आने वाली कठिनाइयों का न्यूनतम योग ज्ञात करना होगा।
इसलिए, यदि इनपुट जॉब्स की तरह है =[2, 3, 4, 6, 3] k =2, तो आउटपुट 8 होगा, पहले हम [2] करते हैं फिर [3, 4, 6, 3] करते हैं। इसलिए कठिनाई 2 + अधिकतम (3, 4, 6, 3) =8 है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- किसी सरणी डीपी को आकार में परिभाषित करें:505 x 15.
- एक फ़ंक्शन dfs() परिभाषित करें, यह प्रारंभ, k, और एक सरणी v, लेगा
- यदि प्रारंभ>=v का आकार, तो −
- रिटर्न (यदि k, 0 के समान है, तो 0, अन्यथा inf)
- यदि k <0, तो −
- वापसी की जानकारी
- यदि dp[start, k] -1 के बराबर नहीं है, तो −
- रिटर्न डीपी[स्टार्ट, के]
- रिट:=जानकारी
- वैल:=0
- इनिशियलाइज़ i :=start के लिए, जब i
- वैल:=अधिकतम वैल और वी[i]
- ret :=न्यूनतम रिट और (val + dfs(i + 1, k-1, v))
उदाहरण (C++)
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e6;
int dp[505][15];
int dfs(int start, int k, vector <int>& v){
if(start >= v.size()){
return k == 0 ? 0 : inf;
}
if(k < 0)
return inf;
if(dp[start][k] != -1)
return dp[start][k];
int ret = inf;
int val = 0;
for(int i = start; i < v.size(); i++){
val = max(val, v[i]);
ret = min(ret, val + dfs(i + 1, k - 1, v));
}
return dp[start][k] = ret;
}
int solve(vector<int>& jobs, int k) {
memset(dp ,-1, sizeof dp);
return dfs(0, k, jobs);
}
int main(){
vector<int> v = {2, 3, 4, 6, 3};
int k = 2;
cout << solve(v, k);
} इनपुट
{2, 3, 4, 6, 3}, 2 आउटपुट
8