Algorithms-K58-PM: Quy hoạch động

1 bình luận cho Algorithms-K58-PM: Quy hoạch động

• 

  27/10/2020 - 14:39

  admin  says:

  C++

  #include <iostream> using namespace std; const int MAX = 200; int a[] = { 0, 3, 1, 2, 0, 4, 3 }; int b[] = { 0, 1, 2, 3, 4, 3, 2, 1 }; int m = 6, n = 7; int kq[MAX][MAX]; int S(int p, int q) { if (p == 0 || q == 0) return 0; if (kq[p][q] == -1) if (a[p] == b[q]) kq[p][q] = S(p-1, q-1) + 1; else kq[p][q] = max(S(p-1, q), S(p, q-1)); return kq[p][q]; } int bottom_up(int p, int q) { for (int i = 0; i < MAX; i++) kq[0][i] = kq[i][0] = 0; for (int i = 1; i <= p; i++) { for (int j = 1; j <= q; j++) if (a[i] == b[j]) kq[i][j] = kq[i-1][j-1] + 1; else kq[i][j] = max(kq[i-1][j], kq[i][j-1]); } return kq[p][q]; } int main() { for (int i = 0; i < MAX; i++) for (int j = 0; j < MAX; j++) kq[i][j] = -1; cout << "De quy co nho: " << S(m, n) << endl; cout << "Bottom-up: " << bottom_up(m, n); } </iostream>

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

  #include <iostream> using namespace std;   const int MAX = 200;   int a[] = { 0, 3, 1, 2, 0, 4, 3 }; int b[] = { 0, 1, 2, 3, 4, 3, 2, 1 }; int m = 6, n = 7;   int kq[MAX][MAX];   int S(int p, int q) { if (p == 0 || q == 0) return 0; if (kq[p][q] == -1) if (a[p] == b[q]) kq[p][q] = S(p-1, q-1) + 1; else kq[p][q] = max(S(p-1, q), S(p, q-1)); return kq[p][q]; }   int bottom_up(int p, int q) { for (int i = 0; i < MAX; i++) kq[0][i] = kq[i][0] = 0; for (int i = 1; i <= p; i++) { for (int j = 1; j <= q; j++) if (a[i] == b[j]) kq[i][j] = kq[i-1][j-1] + 1; else kq[i][j] = max(kq[i-1][j], kq[i][j-1]); } return kq[p][q]; }   int main() { for (int i = 0; i < MAX; i++) for (int j = 0; j < MAX; j++) kq[i][j] = -1; cout << "De quy co nho: " << S(m, n) << endl; cout << "Bottom-up: " << bottom_up(m, n); } </iostream>

  Trả lời