โปรแกรม C++ สำหรับการจัดวงเล็บเหมาะสมด้วย Dynamic Programming

นี่คือโปรแกรม C++ สำหรับทำการจัดวงเล็บเหมาะสม (Optimal Parenthesization) โดยใช้ Dynamic Programming เพื่อหาจำนวนการคูณสเกลาร์น้อยที่สุดในการคูณเมทริกซ์โซ่

อัลกอริทึม

Begin
  รับความยาว n และมิติของเมทริกซ์เป็นอินพุต
  MatrixChain() เพื่อหาจำนวนการคูณน้อยที่สุด:
    Arguments:
      a[i][j] = จำนวนการคูณสเกลาร์ขั้นต่ำที่ต้องการคำนวณเมทริกซ์ A[i]A[i+1]...A[j]
      a[i][j] หมายถึงค่าใช้จ่ายเป็นศูนย์เมื่อคูณเมทริกซ์เดียว
      L = ความยาวโซ่
      m = ค่าใช้จ่าย / การคูณสเกลาร์
  Body of the function:
    for i = 1 ถึง n-1
      เริ่มต้น a[i][i] = 0
    for L = 2 ถึง n-1
      for i = 1 ถึง n - L + 1
        j = i + L - 1
        a[i][j] = INT_MAX
        for k = i ถึง j - 1
          m = a[i][k] + a[k + 1][j] + p[i - 1] * p[k] * p[j]
          if (m < a[i][j])
            a[i][j] = m
            b[i][j] = k
    return a[1][n - 1]
End

ตัวอย่างโค้ด

#include <limits.h>
#include <iostream>
using namespace std;

int MatrixChain(int p[], int n) {
  int a[n][n];
  int b[n][n];
  int i, j, k, L, m;
  for (i = 1; i < n; i++)
    a[i][i] = 0;
  for (L = 2; L < n; L++) {
    for (i = 1; i <= n - L + 1; i++) {
      j = i + L - 1;
      a[i][j] = INT_MAX;
      for (k = i; k <= j - 1; k++) {
        m = a[i][k] + a[k + 1][j] + p[i - 1] * p[k] * p[j];
        if (m < a[i][j]) {
          a[i][j] = m;
          b[i][j] = k;
        }
      }
    }
  }
  return a[1][n - 1];
}

int main() {
  cout << "Enter the length:";
  int n;
  cin >> n;
  int a[n];
  cout << "Enter the dimensions: ";
  for (int v = 0; v < n; ++v) {
    cin >> a[v];
  }
  cout << "Minimum number of multiplications is: " << MatrixChain(a, n);
  return 0;
}

ผลลัพธ์

Enter the length: 5
Enter the dimensions: 2 3 7 6 4
Minimum number of multiplications is: 174