既然已經說到了最長公共子序列，就把這個遞增子序列也說了。同樣的，這里subsequence表明了這樣的子序列不要求是連續的。比如說有子序列{1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 }這樣一個字符串的的最長遞增子序列就是{1,3,4,5,6,7}或者{1,3,4,5,6,19}。
其實這個問題和前面的最長公共子序列問題還是有一定的關聯的。假設我們的初始的序列S1。那我們從小到大先排序一下。得到了S1'。這樣我們再球S1和S1'的最長公共子序列就可以知道答案了：）是不是有點巧妙啊。這個過程還是比較直觀的。但是這個不是這次要說的重點，這個問題有比較傳統的做法的.
我們定義L(j)是一個優化的子結構,也就是最長遞增子序列.那么L(j)和L(1..j-1)的關系可以描述成
L(j) = max {L(i), i<j && Ai<Aj } + 1; 也就是說L(j)等于之前所有的L(i)中最大的的L(i)加一.這樣的L(i)需要滿足的條件就是Ai<Aj.這個推斷還是比較容易理解的.就是選擇j之前所有的滿足小于當前數組的最大值.
很容易的我們寫出了下面的代碼:
-
-
- #include "stdafx.h"
- #include <vector>
- #include <iostream>
- #include "windows.h"
-
-
-
-
-
- template<typename T> void longest_increase_subsequence(const std::vector<T>& s1, std::vector<T>& s2)
- {
-
- int n = s1.size(); if (n<1) return;
- int m = 0;
- int k = 0;
- std::vector<unsigned int> b(n+1, 1);
- std::vector<unsigned int> p(n+1, 0);
-
- for (int i=1;i<=n;i++)
- {
- for (int j=1;j<i;j++)
- {
- if ( s1[i-1] > s1[j-1] && b[i] < b[j] +1 )
- {
- b[i] = b[j] + 1;
- p[i] = j;
- }
- }
- }
- for ( int i=1;i<=n;i++)
- {
- if (m<b[i])
- {
- m = b[i];
- k = i;
- }
- }
- s2.resize(m);
- while (k>0)
- {
- s2[m-1] = s1[k-1];
- m--;
- k = p[k];
- }
- }
- int _tmain(int argc, _TCHAR* argv[])
- {
- int a[] = { 1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 };
- std::vector<int> seq(a, a+sizeof(a)/sizeof(a[0]));
- std::vector<int> r;
- longest_increase_subsequence(seq, r);
- for (int i=0;i<r.size();i++)
- std::cout<<r[i]<<" ";
- std::cout<<std::endl;
- system("pause");
- return 0;
- }
和以往的代碼有些類似,這里還有一些輔助的二維數組p用來回溯最長的這個subsequence.這整個算法的時間復雜度達到了O(n∧2).當然存在一些nlog(n)的實現.但不是動態規劃的重點,這里就不說明了.
重點可以講的是這個問題的擴展.下面的兩個問題也是很經典的問題.
問題1.造橋問題. 原題是這樣:Building Bridges. Consider a 2-D map with a horizontal river passing through its center. There are n cities on the southern bank with x-coordinates a(1) ... a(n) and n cities on the northern bank with x-coordinates b(1) ... b(n). You want to connect as many north-south pairs of cities as possible with bridges such that no two bridges cross. When connecting cities, you can only connect city i on the northern bank to city i on the southern bank. (Note: this problem was incorrectly stated on the paper copies of the handout given in recitation.)
大致就是要在一條河的南北兩邊的各個城市之間造若干座橋．橋兩邊的城市分別是a(1)...a(n)和b(1)...b(n).這里的要求a(i)只可以和b(i)之間造橋,同時兩座橋之間不能交叉.希望可以得到一個盡量多座橋的方案.
比如上面這張圖,初看上去讓人有些沒有思路.但是仔細一想,其實這就是一個完美的最長公共子序列的問題的變形.怎么講呢?如果把河南邊的a城市做一個排序,可以得到一個序列.如上圖,我們得到的就是S1 = {2,1,3,5,4}在這里,同時北邊也進行依次排序,得到序列S2 = {1,2,5,4,3}.進一步從南邊的第一座橋開始計算在北邊序列中的index.也就是S1中的每個值相對于S2中的位置.比如說A2在南邊是第一個在北邊是第二個,所以第一個元素是2.A1在北邊的對應位置是1.A3在北邊的對應位置是5,A5在北邊的對應位置是3,最后一個A4在北邊的對應位置是3.這樣我們就得到一個新的序列S3= {2,1,5,3,4}.這個序列的實際意義就是南邊的第幾座橋需要連接到北邊的第幾座橋.做理想的情況就是遞增的,那樣所有的橋都可以建造:)也就是說我們的造橋問題就轉化成了尋找這個序列的最長遞增子序列的問題.當然就是{1,3,4}.也就是紅線所代表的橋.
代碼不貼了,但是問題確實比較奧妙.
問題2.Box Stacking. You are given a set of n types of rectangular 3-D boxes, where the i^th box has height h(i), width w(i) and depth d(i) (all real numbers). You want to create a stack of boxes which is as tall as possible, but you can only stack a box on top of another box if the dimensions of the 2-D base of the lower box are each strictly larger than those of the 2-D base of the higher box. Of course, you can rotate a box so that any side functions as its base. It is also allowable to use multiple instances of the same type of box.
這個問題的簡要描述就是有若干個不同的箱子.你需要把他疊放的盡量的高.但是箱子的擺放必須滿足大的在下面,小的在上面的原則.箱子可以旋轉且數量不限.要求給出一組箱子就能求出能擺放的最大高度. 其實這個問題也是一個最長遞增子序列的問題.只是隱藏的更深一點. 因為箱子可以翻轉的緣故.我們首先定義我們的箱子的長寬高分別是h,w,d.為了避免重復計算,我們約定w<=d.這樣每個箱子可以改成3個箱子.這樣我們就不用在考慮旋轉的問題了.第一步,我們先把箱子按照w*d的值來排序.(為社么要排序讀者可以自己想想).然后我們的模型就開始用H(j)來表示第j個箱子時這個箱子的高度.記得最長遞增子序列的約束條件是Ai<Aj.這里的條件只是改成了對應的di<dj&&wi<wj.同時原來的+1也變成了+hi.
最后貼一下不是很好的代碼.但是大致上還是工作了:
-
-
- #include "stdafx.h"
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <functional>
- #include "windows.h"
-
-
-
-
-
-
-
-
-
- struct Box
- {
- int h;
- int w;
- int d;
- };
- struct sizeSort: public std::binary_function <Box, Box, bool>
- {
- bool operator()(const Box& b1, const Box& b2)
- {
- return b1.w*b1.d > b2.w*b2.d;
- }
- };
- int highest_box_stacking( const std::vector<Box>& b)
- {
-
-
-
- if (b.size()<1)
- return 0;
- std::vector<Box> box (b.size()*3);
- for (int i=0;i<b.size();i++)
- {
- box[i*3+0].h = b[i].h;
- box[i*3+0].w = b[i].w < b[i].d ? b[i].w : b[i].d;
- box[i*3+0].d = b[i].w < b[i].d ? b[i].d : b[i].w;
- box[i*3+1].h = b[i].w;
- box[i*3+1].w = b[i].h < b[i].d ? b[i].h : b[i].d;
- box[i*3+1].d = b[i].h < b[i].d ? b[i].d : b[i].h;
- box[i*3+2].h = b[i].d;
- box[i*3+2].w = b[i].h < b[i].w ? b[i].h : b[i].w;
- box[i*3+2].d = b[i].h < b[i].w ? b[i].w : b[i].h;
- }
- std::sort(box.begin(),box.end(),sizeSort());
-
- std::vector <int> m(b.size()*3);
- m[0] = box[0].h;
- for ( int i = 1; i < box.size(); i++ )
- {
- for ( int j = 0; j < i; j++ )
- {
- if ( (box[i].w <= box[j].w) && (box[i].d <= box[j].d) && (m[i] < m[j]+box[i].h) )
- m[i] = m[j] + box[i].h;
- }
- }
- return *std::max_element(m.begin(),m.end());
- }
- int _tmain(int argc, _TCHAR* argv[])
- {
- std::vector<Box> box(3);
- box[0].h = 2;
- box[0].w = 3;
- box[0].d = 4;
- box[1].h = 2;
- box[1].w = 3;
- box[1].d = 1;
- box[2].h = 5;
- box[2].w = 3;
- box[2].d = 4;
- std::cout<<highest_box_stacking(box)<<std::endl;
- system("pause");
- return 0;
- }