Chương trình C ++ để tìm ra chi phí để di chuyển tất cả các tọa độ đã cho

Giả sử, chúng ta được cung cấp n tọa độ ba chiều. Chi phí để đi từ tọa độ (a, b, c) đến (x, y, z) là ∣ x - a∣ + ∣ y - b∣ + max (0, z - c). Chúng tôi bắt đầu từ tọa độ đầu tiên, sau đó truy cập tất cả các tọa độ ít nhất một lần, và sau đó quay trở lại tọa độ đầu tiên. Chúng tôi phải tìm ra tổng chi phí của cả chuyến đi này. Các tọa độ được cung cấp cho chúng tôi trong mảng 'coords'.

Vì vậy, nếu đầu vào là n =3, coords ={{1, 1, 0}, {1, 3, 4}, {3, 2, 2}}, thì đầu ra sẽ là 12.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Define one 2D array tpa.
tpa[1, 0] := 0
   for initialize i := 1, when i < 2n, update (increase i by 1), do:
      for initialize j := 0, when j < n, update (increase j by 1), do:
         if i mod 2 is same as 0, then:
            Ignore following part, skip to the next iteration
               for initialize t := 0, when t < n, update (increase t by 1), do:
                  x := first value of coords[t]
                  y := second value of coords[t]
                  z := third value of coords[t]
                  p := first value of coords[j]
                  q := second value of coords[j]
                r := third value of coords[j]
tpa[i OR (1 bitwise left shift t)][t] := minimum of (tpa[i|(1 bitwise left shift t)][t], tpa[i][j] + |x - p| + |y - q| + maximum of (0, z - r))
res := infinity
for initialize i := 0, when i < n, update (increase i by 1), do:
x := first value of coords[0]
y := second value of coords[0]
z := third value of coords[0]
p := first value of coords[i]
q := second value of coords[i]
r := third value of coords[i]
res := minimum of (res and tpa[2n - 1, i] + |x - p| + |y - q| + maximum of (0 and z - r))
return res

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

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

Đầu ra

12