Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

दिए गए निर्देशांकों की यात्रा की लागत ज्ञात करने का C++ प्रोग्राम


मान लीजिए n त्रि-आयामी निर्देशांक दिए गए हैं। निर्देशांक (a, b, c) से (x, y, z) तक यात्रा की लागत |x-a| + |y-b| + max(0, z-c) है। हम पहले निर्देशांक से शुरू करते हैं, फिर सभी निर्देशांकों पर कम से कम एक बार जाते हैं, और फिर पहले निर्देशांक पर लौट आते हैं। हमें इस पूरी यात्रा की कुल लागत ज्ञात करनी है। निर्देशांक 'coords' सरणी में दिए गए हैं।

उदाहरण के लिए, यदि इनपुट है n = 3, coords = {{1, 1, 0}, {1, 3, 4}, {3, 2, 2}}, तो आउटपुट 12 होगा।

चरण

इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:

एक 2D सरणी tpa परिभाषित करें
tpa[1][0] := 0
i := 1 से 2^n-1 तक:
    j := 0 से n-1 तक:
        यदि i % 2 == 0, तो जारी रखें
        t := 0 से n-1 तक:
            x := coords[t] का पहला मान
            y := coords[t] का दूसरा मान
            z := coords[t] का तीसरा मान
            p := coords[j] का पहला मान
            q := coords[j] का दूसरा मान
            r := coords[j] का तीसरा मान
            tpa[i | (1 << t)][t] := min(tpa[i | (1 << t)][t], tpa[i][j] + |x-p| + |y-q| + max(0, z-r))
res := अनंत
i := 0 से n-1 तक:
    x := coords[0] का पहला मान
    y := coords[0] का दूसरा मान
    z := coords[0] का तीसरा मान
    p := coords[i] का पहला मान
    q := coords[i] का दूसरा मान
    r := coords[i] का तीसरा मान
    res := min(res, tpa[2^n-1][i] + |x-p| + |y-q| + max(0, z-r))
res लौटाएँ

उदाहरण

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

#include <bits/stdc++.h> using namespace std; const int INF = 1e9; #define N 100 int solve(int n, vector<tuple<int,int,int>> coords){    vector<vector<int>> tpa(pow(2, n), vector<int>(n, INF));    tpa[1][0] = 0;    for(int i = 1; i < pow(2,n); i++) {       for(int j = 0; j < n; j++){          if(i % 2 == 0)             continue;          for(int t = 0; t < n; t++) {             int x, y, z, p, q, r;             tie(x, y, z) = coords[t];             tie(p, q, r) = coords[j];             tpa[i | (1 << t)][t] = min(tpa[i|(1 << t)][t], tpa[i][j] + abs(x - p) + abs(y - q) + max(0, z - r));          }       }    }    int res = INF;    for(int i = 0; i < n; i++) {       int x, y, z, p, q, r;       tie(x, y, z) = coords[0];       tie(p, q, r) = coords[i];       res = min(res, tpa[pow(2, n) - 1][i] + abs(x - p) + abs(y - q) + max(0, z - r));    }    return res; } int main() {    int n = 3;    vector<tuple<int,int,int>> coords = {{1, 1, 0}, {1, 3, 4}, {3, 2, 2}};    cout<< solve(n, coords);    return 0; }

इनपुट

3, {{1, 1, 0}, {1, 3, 4}, {3, 2, 2}}

आउटपुट

12
  1. ग्राफ में सुपर वर्टेक्स खोजने का C++ प्रोग्राम ग्राफ में सुपर वर्टेक्स खोजने का C++ प्रोग्राम

    मान लीजिए n वर्टेक्स वाला एक ग्राफ दिया गया है। वर्टेक्स 1 से n तक संख्याबद्ध हैं और edges सरणी में दी गई एज्स से जुड़े हैं। प्रत्येक वर्टेक्स का एक x मान है जो 1 से n के बीच होता है, यह values सरणी में दिया गया है। हमें ग्राफ में सुपर वर्टेक्स खोजने हैं। एक वर्टेक्स i को सुपर वर्टेक्स कहा जाता है

  1. दिए गए ग्राफ में ब्रिज एज की संख्या ज्ञात करने का C++ प्रोग्राम दिए गए ग्राफ में ब्रिज एज की संख्या ज्ञात करने का C++ प्रोग्राम

    मान लीजिए n वर्टेक्स और m एज वाला एक अनभारित, निदेश रहित ग्राफ दिया गया है। ग्राफ में एक ब्रिज एज वह एज है जिसे हटाने से ग्राफ असंबद्ध हो जाता है। हमें दिए गए ग्राफ में ऐसी एज की संख्या ज्ञात करनी है। ग्राफ में समानांतर एज या सेल्फ-लूप नहीं हैं। उदाहरण के लिए, यदि इनपुट है n = 5, m = 6, edges = {{1

  1. - पायथन में सभी को खरीदने की न्यूनतम लागत ज्ञात करने का प्रोग्राम

    मान लीजिए, हमारे पास N आइटम हैं, जिन्हें 0, 1, 2, ..., N-1 के रूप में चिह्नित किया गया है। फिर, हमें sets नामक आकार S की एक 2D सूची दी जाती है। यहां, हम i-th सेट को कीमत sets[i,2] पर खरीद सकते हैं, और हमें sets[i, 0] से sets[i, 1] तक का हर आइटम प्राप्त होता है। साथ ही, हमारे पास removals नामक आकार