dynamicprogramming.h

它建立在最优原则的基础上,采用动态规划方法,可以优雅而高效地解决许多用贪心技术或分治技术无法解决的问题。因此,动态规划技术越来越成为解决许多重要的应用问题的关键技术。矩阵连乘。

/**
 * File    : DynamicProgramming.h
 * Author  : Wind
 * Email   : [e-mail]
 * Date    : 2005-9-29
 * Purpose : Dynamic Programming practise
 * */

#include "../head/Matrix.h"

#ifndef DYNAMICPROGRAMMING_H_
#define DYNAMICPROGRAMMING_H_

/**
 * @describ Calculate the multiply orders of matrixs.
 * @param (Matrix matrixs[])      The matrixs to be calculate.
 * @param (int miniMultTable[])   The integer array to store the minimun multiply times. 
 *                                eg: minimultTalb[i,j] store the minimun multiply times of matrixs 
 *                                that start from matrix[i] to matrix[j].
 * @param (int bestBrokenTable[]) The integer array to store the best best broken positions.
 *                                eg: bestBrokenTable[i,j] presents the best broken position of the matrixs multiply
 *                                that start from matrix[i] to matrix[j].
 * @param (int matrixNum)         The length of matrixs[]
 * @param (int m)                 The Chain order start position.
 * @param (int n)                 The Chain order end position.
 * @return                        The minimun multiply times of matrixs that start from matrix[m] to matrix[n]. 
 * */
int matrixChainOrder(Matrix matrixs [],int miniMultTable [] , int bestBrokenTable [],int matrixNum,int m,int n );

/**
 * @describ Multiply the matrixs starts from in the best order depending on the best broken table. 
 * @param (int bestBrokenTable [])  Integer array that stores the best broken positions.
 * @param (int tableLength)         Length of bestBrokenTable [].
 * @param (int tbColLength)         Coloumn length of bestBrokenTable [].
 * @param (int m)                   Multiply start position.
 * @param (int n)                   Multiply end position.
 * @param (char * order)            String that to store and presents the multiply orders.
 * @return                          String that that presents the multiply orders.
 * */
char * matrixChainMultiply(int bestBrokenTable [],int tableLength,int tbColLength,
                           int m, int n,char * order);

typedef struct {
    double weight;
    double value;
} Item;

#endif /*DYNAMICPROGRAMMING_H_*/