Dynamic Programming(2)

可以用动态规划解决的几个常见问题：

---

• 组合问题中的动态规划：
  
  1. 0-1背包问题；
  2. 最长公共子序列(包括连续的和非连续的两种，都可以用DP做，不过连续的用suffix tree做可以达到O(n)的时间复杂度)；
  3. 最大子段和问题，即求一个数列中和为最大的一个连续子段(DP需要O(n)就可以解决，brute force最少要O(n^2), 分治要O(nlgn)，DP费时最短)；
  4. 硬币找换问题
  
  
• 图问题中有：
  1. TSP问题(travelling salesman problem)：旅行n个城市，要求各个城市经历且仅经历一次，然后回到出发城市，要求所走的路程最短；
  2. 多段图的最短路径
  
  
• 查找问题：
  1. 最优二叉查找树(注意与Hofmann编码树区别开)；
  2. 近似串匹配问题
  
  
• 其他：
  1. 装配线调度问题；
  2. 矩阵连乘法问题
  
  

     【注：学习DP，《算法导论》和《算法设计与分析》都是不错的教材。】
     其实能用DP解决的问题很多都可以用回朔剪枝或分治解决。

Dynamic Programming(1)

连续的笔试面试，碰到了好几次动态规划的题，都没有写全，终于下定决心来搞定它，权当笔记，行家莫笑。
有DP解的算法问题要求两个条件：1) 最优子结构 2)重叠子问题，这是DP的核心。一下分别列出几个经典的DP问题。

---

1. 0-1背包问题
在一定容量的背包中放物品，求得到价值最大的情况，代码如下所示：

int set_package(int* W, int* V, int n, int C);
int main()
{
   int W[] = {35, 30, 60, 50, 40, 10, 25};      // 物体重量
   int V[] = {10, 40, 30, 50, 35, 40, 30};      // 物体价值
   int n = 7;                                   // 几个物体
   int capacity = 150;                          //  背包容量
   int value = set_package(W, V, n, capacity);  // 动态规划
   cout << "Total max value is: " << value << endl;
}  

// W: 重量,  V: 价值,  n: 物体种类  C: 背包容量 
int set_package(int* W, int* V, int n, int C) 
{     
    int i, j;     
    int** tabv = new int*[C+1];  
    // 存放动态规划临时结果     
    for (i = 0; i <= C; i++)
         tabv[i] = new int[n+1];
    bool* index = new bool[n];    // 某一物体是否被放入背包      
    for (i = 0; i <=C; i++)       // 初始化最左一列和最下一行  
         tabv[i][0] = 0;     
    for (j = 0; j <= n; j++)  
         tabv[0][j] = 0;          
    
    // 在每个容量i下，去装前j个物体所能达到的最大价值放入tabv[i][j]中     
    for (i = 1; i <= C; i++){         
        for (j = 1; j <= n; j++) {      
            if (i >= W[j-1]) // 若背包能装下j物体，W[j-1]代表j物体重量
         tabv[i][j] = cal_max(V[j-1]+tabv[i-W[j-1]][j-1], tabv[i][j-1]);
     else
  tabv[i][j] = tabv[i][j-1]; 
               // 若装不下，则最大价值就是前j-1个物体最大价值
 }
    }

   // 从tabv数组反求物体列表
   i = C;
   for (j = n; j > 0; --j) {
   // 如果i容量下，装前j个物体价值大于前j-1个物体最大价值，则第j个物体肯定被装到包里
        if (tabv[i][j] > tabv[i][j-1]) {    
              index[j-1] = true;
              i -= W[j-1];  // substract weight of the jth object
         }
         else
              index[j-1] = false; //
   }

   // 打印结果，省略...
   return tabv[C][n];   //返回结果
}

    这里中间过程的表格其实可以缩减到一维，因为tabv[i][j]只用到j-1列的值，所以可以改进空间复杂度为O(C)而非O(nC)，这个比较简单，就不贴上来了。值得注意的是这样要找到哪几个物体被选中就变得复杂一些，需要中间记下一些变量。

从此，这个就是我的技术博了

三分薄田，可以耕耘，不求收获，只求记忆。