C++ में k दिनों में जॉब्स पूरा करने के लिए कठिनाई के न्यूनतम योग का प्रोग्राम

समस्या विवरण

मान लीजिए हमारे पास jobs नामक संख्याओं की एक सूची और एक मान k है। अब हम सभी जॉब्स को k अलग-अलग दिनों में पूरा करना चाहते हैं। जॉब्स को दिए गए क्रम में किया जाना चाहिए और प्रत्येक दिन हमें एक टास्क पूरा करना होगा। जॉब i की कठिनाई jobs[i] पर संग्रहीत है और एक दिन में जॉब्स की सूची पूरी करने की कठिनाई उस दिन किए गए अधिकतम कठिनाई वाले जॉब की होगी। तो हमें k अलग-अलग दिनों में जॉब्स करने के लिए कठिनाई के न्यूनतम योग को ढूंढना है।

उदाहरण के लिए, यदि इनपुट है jobs = [2, 3, 4, 6, 3] k = 2, तो आउटपुट 8 होगा, पहले हम [2] करते हैं फिर [3, 4, 6, 3] करते हैं। तो कठिनाई 2 + max(3, 4, 6, 3) = 8 है।

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए हम मेमोइजेशन के साथ डायनामिक प्रोग्रामिंग का उपयोग करेंगे:

1. आकार 505×15 का एक ऐरे dp परिभाषित करें
2. एक फंक्शन dfs() परिभाषित करें जो start, k, और ऐरे v लेता है
   • यदि start >= v का आकार, तो (यदि k == 0 तो 0 अन्यथा अनंत) वापस करें
   • यदि k < 0, तो अनंत वापस करें
   • यदि dp[start][k] != -1, तो dp[start][k] वापस करें
   • ret := अनंत
   • val := 0
   • i := start से v के आकार तक:
     • val := max(val, v[i])
     • ret := min(ret, val + dfs(i+1, k-1, v))
   • dp[start][k] = ret
   • ret वापस करें
3. मुख्य विधि से:
   • dp को -1 से भरें
   • dfs(0, k, jobs) वापस करें

उदाहरण

#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