既然已經(jīng)說到了最長(zhǎng)公共子序列，就把這個(gè)遞增子序列也說了。同樣的，這里subsequence表明了這樣的子序列不要求是連續(xù)的。比如說有子序列{1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 }這樣一個(gè)字符串的的最長(zhǎng)遞增子序列就是{1,3,4,5,6,7}或者{1,3,4,5,6,19}。
其實(shí)這個(gè)問題和前面的最長(zhǎng)公共子序列問題還是有一定的關(guān)聯(lián)的。假設(shè)我們的初始的序列S1。那我們從小到大先排序一下。得到了S1'。這樣我們?cè)偾騍1和S1'的最長(zhǎng)公共子序列就可以知道答案了：）是不是有點(diǎn)巧妙啊。這個(gè)過程還是比較直觀的。但是這個(gè)不是這次要說的重點(diǎn)，這個(gè)問題有比較傳統(tǒng)的做法的.
我們定義L(j)是一個(gè)優(yōu)化的子結(jié)構(gòu),也就是最長(zhǎng)遞增子序列.那么L(j)和L(1..j-1)的關(guān)系可以描述成
L(j) = max {L(i), i<j && Ai<Aj } + 1; 也就是說L(j)等于之前所有的L(i)中最大的的L(i)加一.這樣的L(i)需要滿足的條件就是Ai<Aj.這個(gè)推斷還是比較容易理解的.就是選擇j之前所有的滿足小于當(dāng)前數(shù)組的最大值.
很容易的我們寫出了下面的代碼:
-
-
- #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;
- }
和以往的代碼有些類似,這里還有一些輔助的二維數(shù)組p用來回溯最長(zhǎng)的這個(gè)subsequence.這整個(gè)算法的時(shí)間復(fù)雜度達(dá)到了O(n∧2).當(dāng)然存在一些nlog(n)的實(shí)現(xiàn).但不是動(dòng)態(tài)規(guī)劃的重點(diǎn),這里就不說明了.
重點(diǎn)可以講的是這個(gè)問題的擴(kuò)展.下面的兩個(gè)問題也是很經(jīng)典的問題.
問題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.)
大致就是要在一條河的南北兩邊的各個(gè)城市之間造若干座橋．橋兩邊的城市分別是a(1)...a(n)和b(1)...b(n).這里的要求a(i)只可以和b(i)之間造橋,同時(shí)兩座橋之間不能交叉.希望可以得到一個(gè)盡量多座橋的方案.
比如上面這張圖,初看上去讓人有些沒有思路.但是仔細(xì)一想,其實(shí)這就是一個(gè)完美的最長(zhǎng)公共子序列的問題的變形.怎么講呢?如果把河南邊的a城市做一個(gè)排序,可以得到一個(gè)序列.如上圖,我們得到的就是S1 = {2,1,3,5,4}在這里,同時(shí)北邊也進(jìn)行依次排序,得到序列S2 = {1,2,5,4,3}.進(jìn)一步從南邊的第一座橋開始計(jì)算在北邊序列中的index.也就是S1中的每個(gè)值相對(duì)于S2中的位置.比如說A2在南邊是第一個(gè)在北邊是第二個(gè),所以第一個(gè)元素是2.A1在北邊的對(duì)應(yīng)位置是1.A3在北邊的對(duì)應(yīng)位置是5,A5在北邊的對(duì)應(yīng)位置是3,最后一個(gè)A4在北邊的對(duì)應(yīng)位置是3.這樣我們就得到一個(gè)新的序列S3= {2,1,5,3,4}.這個(gè)序列的實(shí)際意義就是南邊的第幾座橋需要連接到北邊的第幾座橋.做理想的情況就是遞增的,那樣所有的橋都可以建造:)也就是說我們的造橋問題就轉(zhuǎn)化成了尋找這個(gè)序列的最長(zhǎng)遞增子序列的問題.當(dāng)然就是{1,3,4}.也就是紅線所代表的橋.
代碼不貼了,但是問題確實(shí)比較奧妙.
問題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.
這個(gè)問題的簡(jiǎn)要描述就是有若干個(gè)不同的箱子.你需要把他疊放的盡量的高.但是箱子的擺放必須滿足大的在下面,小的在上面的原則.箱子可以旋轉(zhuǎn)且數(shù)量不限.要求給出一組箱子就能求出能擺放的最大高度. 其實(shí)這個(gè)問題也是一個(gè)最長(zhǎng)遞增子序列的問題.只是隱藏的更深一點(diǎn). 因?yàn)橄渥涌梢苑D(zhuǎn)的緣故.我們首先定義我們的箱子的長(zhǎng)寬高分別是h,w,d.為了避免重復(fù)計(jì)算,我們約定w<=d.這樣每個(gè)箱子可以改成3個(gè)箱子.這樣我們就不用在考慮旋轉(zhuǎn)的問題了.第一步,我們先把箱子按照w*d的值來排序.(為社么要排序讀者可以自己想想).然后我們的模型就開始用H(j)來表示第j個(gè)箱子時(shí)這個(gè)箱子的高度.記得最長(zhǎng)遞增子序列的約束條件是Ai<Aj.這里的條件只是改成了對(duì)應(yīng)的di<dj&&wi<wj.同時(shí)原來的+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;
- }