本文關(guān)鍵詞：算法設計，由筆耕文化傳播整理發(fā)布。

根據(jù)實例，可以理出追蹤解的思路，代碼如下：

void TrackSolution(int v[N],int w[N],int tagi[][B+1]){ //x[i-1]標記第i件物品的件數(shù) int x[N]; for(int i=0;i<N;i++) x[i]=0; int y=B,j=tagi[N][B]; while (tagi[j][y]!=0){ j=tagi[j][y]; //標記函數(shù)最下角ik(y)標記的物品取一件 x[j-1]=1; y=y-w[j-1]; while (tagi[j][y]==j){ y=y-w[j]; x[j-1]=x[j-1]+1; } } }運行結(jié)果：

背包問題是很經(jīng)典的動態(tài)規(guī)劃問題，很多問題都是背包的變種，比如下面兩個題目：

第一個題目其實就是0-1背包問題，即看做價值和重量相等（都為ai）的物品裝入背包，每件物品最多選1件，總重不能超過K，總價值最大的問題。設Fk(y)表示只允許前k個下載請求，最大帶寬不超過y時利用最大限度的帶寬數(shù)。遞推關(guān)系和邊界條件如下：

注意0-1背包和背包問題的遞推關(guān)系主要區(qū)別是：當選擇第k件物品時，F(xiàn)k(y)表示為Fk-1(y-wk)+vk，而非Fk(y-wk)+vk，即只能在前k-1件物品里繼續(xù)選擇。另外F1(y)的邊界函數(shù)也不同。

至于第二個題目，其實就是使得一條加工線上的加工時間不超過T/2時加工時間盡可能大的問題，和第一個問題是一樣的。

代碼下載：

參考資料：屈婉玲 劉田等 《算法設計與分析》

  本文關(guān)鍵詞：算法設計，由筆耕文化傳播整理發(fā)布。