標籤: 暫無標籤

動態規劃(dynamic programming)是運籌學的一個分支,是求解決策過程(decision process)最優化的數學方法。20世紀50年代初美國數學家R.E.Bellman等人在研究多階段決策過程(multistep decision process)的優化問題時,提出了著名的最優化原理(principle of optimality),把多階段過程轉化為一系列單階段問題,利用各階段之間的關係,逐個求解,創立了解決這類過程優化問題的新方法——動態規劃。1957年出版了他的名著Dynamic Programming,這是該領域的第一本著作。

1簡介

動態規劃
是信息學競賽中選手必須熟練掌握的一種演算法,他以其多元性廣受出題者的喜愛.
動態規劃首次進入信息學奧賽是在IOI94(數字三角形),在國內首次出現是在NOI95。此後動態規劃成為信息學奧賽的必考演算法之一。

2分類

動態規劃一般可分為線性動規,區域動規,樹形動規,背包動規四類。
舉例
區域動規
石子合併, 加分二叉樹,統計單詞個數,炮兵布陣等
背包問題
01背包問題,完全背包問題,分組背包問題,二維背包,裝箱問題,擠牛奶(同濟ACM第1132題)等
應用實例
最短路徑問題 ,項目管理,網路流優化等

3概念意義

動態規劃問世以來,在經濟管理、生產調度、工程技術和最優控制等方面得到了廣泛的應用。例如最短路線、庫存管理、資源分配、設備更新、排序、裝載等問題,用動態規劃方法比用其它方法求解更為方便。
雖然動態規劃主要用於求解以時間劃分階段的動態過程的優化問題,但是一些與時間無關的靜態規劃(如線性規劃、非線性規劃),只要人為地引進時間因素,把它視為多階段決策過程,也可以用動態規劃方法方便地求解。
動態規劃程序設計是對解最優化問題的一種途徑、一種方法,而不是一種特殊演算法。不象搜索或數值計算那樣,具有一個標準的數學表達式和明確清晰的解題方法。動態規劃程序設計往往是針對一種最優化問題,由於各種問題的性質不同,確定最優解的條件也互不相同,因而動態規劃的設計方法對不同的問題,有各具特色的解題方法,而不存在一種萬能的動態規劃演算法,可以解決各類最優化問題。因此讀者在學習時,除了要對基本概念和方法正確理解外,必須具體問題具體分析處理,以豐富的想象力去建立模型,用創造性的技巧去求解。我們也可以通過對若干有代表性的問題的動態規劃演算法進行分析、討論,逐漸學會並掌握這一設計方法。

4基本模型

多階段決策過程的最優化問題。
含有遞推的思想以及各種數學原理(加法原理,乘法原理等等)。
在現實生活中,有一類活動的過程,由於它的特殊性,可將過程分成若干個互相聯繫的階段,在它的每一階段都需要作出決策,從而使整個過程達到最好的活動效果。當然,各個階段決策的選取不是任意確定的,它依賴於當前面臨的狀態,又影響以後的發展,當各個階段決策確定后,就組成一個決策序列,因而也就確定了整個過程的一條活動路線,如圖所示:(看詞條圖)
多階段決策問題

  多階段決策問題

這種把一個問題看作是一個前後關聯具有鏈狀結構的多階段過程就稱為多階段決策過程,這種問題就稱為多階段決策問題。

5基本思想

動態規劃演算法通常用於求解具有某種最優性質的問題。在這類問題中,可能會有許多可行解。每一個解都對應於一個值,我們希望找到具有最優值的解。動態規劃演算法與分治法類似,其基本思想也是將待求解問題分解成若干個子問題,先求解子問題,然後從這些子問題的解得到原問題的解。與分治法不同的是,適合於用動態規劃求解的問題,經分解得到子問題往往不是互相獨立的。若用分治法來解這類問題,則分解得到的子問題數目太多,有些子問題被重複計算了很多次。如果我們能夠保存已解決的子問題的答案,而在需要時再找出已求得的答案,這樣就可以避免大量的重複計算,節省時間。我們可以用一個表來記錄所有已解的子問題的答案。不管該子問題以後是否被用到,只要它被計算過,就將其結果填入表中。這就是動態規劃法的基本思路。具體的動態規劃演算法多種多樣,但它們具有相同的填表格式。

6基本結構

多階段決策問題中,各個階段採取的決策,一般來說是與時間有關的,決策依賴於當前狀態,又隨即引起狀態的轉移,一個決策序列就是在變化的狀態中產生出來的,故有「動態」的含義,稱這種解決多階段決策最優化問題的方法為動態規劃方法。

7基本模型

根據上例分析和動態規劃的基本概念,可以得到動態規劃的基本模型如下:
(1)確定問題的決策對象。 (2)對決策過程劃分階段。 (3)對各階段確定狀態變數。 (4)根據狀態變數確定費用函數和目標函數。 (5)建立各階段狀態變數的轉移過程,確定狀態轉移方程。

8適用條件

任何思想方法都有一定的局限性,超出了特定條件,它就失去了作用。同樣,動態規劃也並不是萬能的。適用動態規劃的問題必須滿足最優化原理和無後效性。
1.最優化原理(最優子結構性質) 最優化原理可這樣闡述:一個最優化策略具有這樣的性質,不論過去狀態和決策如何,對前面的決策所形成的狀態而言,餘下的諸決策必須構成最優策略。簡而言之,一個最優化策略的子策略總是最優的。一個問題滿足最優化原理又稱其具有最優子結構性質。
2.無後效性 將各階段按照一定的次序排列好之後,對於某個給定的階段狀態,它以前各階段的狀態無法直接影響它未來的決策,而只能通過當前的這個狀態。換句話說,每個狀態都是過去歷史的一個完整總結。這就是無後向性,又稱為無後效性。
3.子問題的重疊性 動態規劃將原來具有指數級時間複雜度的搜索演算法改進成了具有多項式時間複雜度的演算法。其中的關鍵在於解決冗餘,這是動態規劃演算法的根本目的。動態規劃實質上是一種以空間換時間的技術,它在實現的過程中,不得不存儲產生過程中的各種狀態,所以它的空間複雜度要大於其它的演算法。

9作用

在編程中常用解決最長公共子序列問題、矩陣連乘問題、凸多邊形最優三角剖分問題、電路布線等問題。
決策
決策:
當前狀態通過決策,回到了以前狀態.可見決策其實就是狀態之間的橋樑。而以前狀態也就決定了當前狀態的情況。數字三角形的決策就是選擇相鄰的兩個以前狀態的最優值。

狀態

狀態:
我們一般在動規的時候所用到的一些數組,也就是用來存儲每個狀態的最優值的。我們就從動態規劃的要訣,也就是核心部分「狀態」開始,來逐步了解動態規劃。有時候當前狀態確定后,以前狀態就已經確定,則無需枚舉.

10應用

一、動態規劃的概念
近年來,涉及動態規劃的各種競賽題越來越多,每一年的NOI幾乎都至少有一道題目需要用動態規劃的方法來解決;而競賽對選手運用動態規劃知識的要求也越來越高,已經不再停留於簡單的遞推和建模上了。
要了解動態規劃的概念,首先要知道什麼是多階段決策問題。
1. 多階段決策問題
如果一類活動過程可以分為若干個互相聯繫的階段,在每一個階段都需作出決策(採取措施),一個階段的決策確定以後,常常影響到下一個階段的決策,從而就完全確定了一個過程的活動路線,則稱它為多階段決策問題。
各個階段的決策構成一個決策序列,稱為一個策略。每一個階段都有若干個決策可供選擇,因而就有許多策略供我們選取,對應於一個策略可以確定活動的效果,這個效果可以用數量來確定。策略不同,效果也不同,多階段決策問題,就是要在可以選擇的那些策略中間,選取一個最優策略,使在預定的標準下達到最好的效果.
2.動態規劃問題中的術語
階段:把所給求解問題的過程恰當地分成若干個相互聯繫的階段,以便於求解,過程不同,階段數就可能不同.描述階段的變數稱為階段變數。在多數情況下,階段變數是離散的,用k表示。此外,也有階段變數是連續的情形。如果過程可以在任何時刻作出決策,且在任意兩個不同的時刻之間允許有無窮多個決策時,階段變數就是連續的。
在前面的例子中,第一個階段就是點A,而第二個階段就是點A到點B,第三個階段是點B到點C,而第四個階段是點C到點D。
狀態:狀態表示每個階段開始面臨的自然狀況或客觀條件,它不以人們的主觀意志為轉移,也稱為不可控因素。在上面的例子中狀態就是某階段的出發位置,它既是該階段某路的起點,同時又是前一階段某支路的終點。
不可控因素

  不可控因素

在前面的例子中,第一個階段有一個狀態即A,而第二個階段有兩個狀態B1和B2,第三個階段是三個狀態C1,C2和C3,而第四個階段又是一個狀態D。
過程的狀態通常可以用一個或一組數來描述,稱為狀態變數。一般,狀態是離散的,但有時為了方便也將狀態取成連續的。當然,在現實生活中,由於變數形式的限制,所有的狀態都是離散的,但從分析的觀點,有時將狀態作為連續的處理將會有很大的好處。此外,狀態可以有多個分量(多維情形),因而用向量來代表;而且在每個階段的狀態維數可以不同。
狀態變數

  狀態變數

當過程按所有可能不同的方式發展時,過程各段的狀態變數將在某一確定的範圍內取值。狀態變數取值的集合稱為狀態集合。
無後效性:我們要求狀態具有下面的性質:如果給定某一階段的狀態,則在這一階段以後過程的發展不受這階段以前各段狀態的影響,所有各階段都確定時,整個過程也就確定了。換句話說,過程的每一次實現可以用一個狀態序列表示,在前面的例子中每階段的狀態是該線路的始點,確定了這些點的序列,整個線路也就完全確定。從某一階段以後的線路開始,當這
無後效性

  無後效性

段的始點給定時,不受以前線路(所通過的點)的影響。狀態的這個性質意味著過程的歷史只能通過當前的狀態去影響它的未來的發展,這個性質稱為無後效性。
決策:一個階段的狀態給定以後,從該狀態演變到下一階段某個狀態的一種選擇(行動)稱為決策。在最優控制中,也稱為控制。在許多問題中,決策可以自然而然地表示為一個數或一組數。不同的決策對應著不同的數值。描述決策的變數稱決策變數,因狀態滿足無後效性,故在每個階段選擇決策時只需考慮當前的狀態而無須考慮過程的歷史。
決策變數的範圍稱為允許決策集合。
允許決策集合

  允許決策集合

策略:由每個階段的決策組成的序列稱為策略。對於每一個實際的多階段決策過程,可供選取的策略有一定的範圍限制,這個範圍稱為允許策略集合。允許策略
最優策略

  最優策略

集合中達到最優效果的策略稱為最優策略
給定k階段狀態變數x(k)的值后,如果這一階段的決策變數一經確定,第k+1階段的狀態變數x(k+1)也就完全確定,即x(k+1)的值隨x(k)和第k階段的決策u(k)的值變化而變化,那麼
狀態轉移方程

  狀態轉移方程

可以把這一關係看成(x(k),u(k))與x(k+1)確定的對應關係,用x(k+1)=Tk(x(k),u(k))表示。這是從k階段到k+1階段的狀態轉移規律,稱為狀態轉移方程。
最優化原理:作為整個過程的最優策略,它滿足:相對前面決策所形成的狀態而言,餘下的子策略必然構成「最優子策略」。一個問題滿足最優化原理也稱其擁有最優子結構性質。
最優性原理實際上是要求問題的最優策略的子策略也是最優。讓我們通過對前面的例子再分析來具體說明這一點:從A到D,我們知道,最短路徑是AB1C2D,這些點的選擇構成了這個例子的最優策略,根據最優性原理,這個策略的每個子策略應是最優:
最優化原理

  最優化原理

AB1C2是A到C2的最短路徑,B1C2D也是B1到D的最短路徑……──事實正是如此,因此我們認為這個例子滿足最優性原理的要求。

11練習題

USACO
2.2 Subset Sums
題目如下:
對於從1到N的連續整數集合,能劃分成兩個子集合,且保證每個集合的數字和是相等的。
舉個例子,如果N=3,對於{1,2,3}能劃分成兩個子集合,他們每個的所有數字和是相等的:
{3}and {1,2}
這是唯一一種分發(交換集合位置被認為是同一種劃分方案,因此不會增加劃分方案總數)
如果N=7,有四種方法能劃分集合{1,2,3,4,5,6,7},每一種分發的子集合各數字和是相等的:
{1,6,7} and {2,3,4,5} {注 1+6+7=2+3+4+5}
{2,5,7} and {1,3,4,6}
{3,4,7} and {1,2,5,6}
{1,2,4,7} and {3,5,6}
給出N,你的程序應該輸出劃分方案總數,如果不存在這樣的劃分方案,則輸出0。程序不能預存結果直接輸出。
PROGRAM NAME: subset
INPUT FORMAT
輸入文件只有一行,且只有一個整數N
SAMPLE INPUT (file subset . in)
7
OUTPUT FORMAT
輸出劃分方案總數,如果不存在則輸出0。
SAMPLE OUTPUT (file subset.out)
4
參考程序如下(C++語言):
#include <fstream>
using namespace std;
const unsigned int MAX_SUM = 1024;
int n;
unsigned long long int dyn[MAX_SUM];
ifstream fin ("subset. in");
ofstream fout ("subset.out");
int main() {
fin >> n;
fin.close();
int s = n*(n+1);
if (s % 4) {
fout << 0 << endl;
fout.close ();
return ;
}
s /= 4;
int i, j;
dyn [0] = 1;
for (i = 1; i <= n; i++)
for (j = s; j >= i; j--)
dyn[j] += j-i;
fout << (dyn[s]/2) << endl;
fout.close();
return 0;
}
USACO 2.3
Longest Prefix
題目如下:
在生物學中,一些生物的結構是用包含其要素的大寫字母序列來表示的。生物學家對於把長的序列分解成較短的(稱之為元素的)序列很感興趣。
如果一個集合 P 中的元素可以通過並運算(允許重複;並,即∪,相當於 Pascal 中的 「+」 運算符)組成一個序列 S ,那麼我們認為序列 S 可以分解為 P 中的元素。並不是所有的元素都必須出現。舉個例子,序列 ABABACABAAB 可以分解為下面集合中的元素:
{A, AB, BA, CA, BBC}
序列 S 的前面 K 個字元稱作 S 中長度為 K 的前綴。設計一個程序,輸入一個元素集合以及一個大寫字母序列,計算這個序列最長的前綴的長度。
PROGRAM NAME: prefix
INPUT FORMAT
輸入數據的開頭包括 1..200 個元素(長度為 1..10 )組成的集合,用連續的以空格分開的字元串表示。字母全部是大寫,數據可能不止一行。元素集合結束的標誌是一個只包含一個 「.」 的行。集合中的元素沒有重複。接著是大寫字母序列 S ,長度為 1..200,000 ,用一行或者多行的字元串來表示,每行不超過 76 個字元。換行符並不是序列 S 的一部分。
SAMPLE INPUT (file prefix. in)
A AB BA CA BBC
.
ABABACABAABC
OUTPUT FORMAT
只有一行,輸出一個整數,表示 S 能夠分解成 P 中元素的最長前綴的長度。
SAMPLE OUTPUT (file prefix.out)
11
示常式序如下:
#include <stdio.h>
"
#define MAXP 200
"
#define MAXL 10
char prim[MAXP+1][MAXL+1]; "
int nump; "
int start[200001]; "
char data[200000]; "
int ndata; "
int main(int argc, char **argv)
{
FILE *fout, *fin;
int best;
int lv, lv2, lv3;
if ((fin = fopen("prim. in", "r")) == NULL)
{
perror ("fopen fin");
exit(1);
}
if ((fout = fopen("prim.out", "w")) == NULL)
{
perror ("fopen fout");
exit(1);
}
"
while (1)
{
fscanf (fin, "%s", prim[nump]);
if (prim[nump][0] != '.') nump++;
else break;
}
"
ndata = 0;
while (fscanf (fin, "%s", data+ndata) == 1)
ndata += strlen(data+ndata);
start[0] = 1;
best = 0;
for (lv = 0; lv < ndata; lv++)
if (start[lv])
{ "
best = lv; "
"
for (lv2 = 0; lv2 < nump; lv2++)
{
for (lv3 = 0; lv + lv3 < ndata && prim[lv2][lv3] &&
prim[lv2][lv3] == data[lv+lv3]; lv3++)
;
if (!prim[lv2][lv3]) "
start[lv + lv3] = 1; "
}
}
"
if (start[ndata]) best = ndata;
fprintf (fout, "%i\n", best);
return 0;
}
USACO 3.1
Score Inflation
題目如下:
我們試著設計我們的競賽以便人們能儘可能的多得分,這需要你的幫助。
我們可以從幾個種類中選取競賽的題目,這裡的一個"種類"是指一個競賽題目的集合,解決集合中的題目需要相同多的時間並且能得到相同的分數。
你的任務是寫一個程序來告訴USACO的職員,應該從每一個種類中選取多少題目,使得解決題目的總耗時在競賽規定的時間裡並且總分最大。
輸入包括競賽的時間,M(1 <= M <= 10,000)和N,"種類"的數目1 <= N <= 10,000。
後面的每一行將包括兩個整數來描述一個"種類":
第一個整數說明解決這種題目能得的分數(1 <= points <= 10000),第二整數說明解決這種題目所需的時間(1 <= minutes <= 10000)。
你的程序應該確定我們應該從每個"種類"中選多少道題目使得能在競賽的時間中得到最大的分數。
來自任意的"種類"的題目數目可能任何非負數(0或更多)。
計算可能得到的最大分數。
PROGRAM NAME: inflate
INPUT FORMAT
第 1 行: M, N--競賽的時間和題目"種類"的數目。
第 2-N+1 行: 兩個整數:每個"種類"題目的分數和耗時。
SAMPLE INPUT (file inflate .in)
300 4
100 60
250 120
120 100
35 20
OUTPUT FORMAT
單獨的一行包括那個在給定的限制里可能得到的最大的分數。
SAMPLE OUTPUT (file inflate.out)
605
{從第2個"種類"中選兩題,第4個"種類"中選三題}
示常式序如下:
#include <fstream.h>
ifstream fin("inflate .in");
ofstream fout("inflate.out");
const short maxm = 10010;
long best[maxm], m, n;
void
main()
{
short i, j, len, pts;
fin >> m >> n;
for (j = 0; j <= m; j++)
best[j] = 0;
for (i = 0; i < n; i++) {
fin >> pts >> len;
for (j = len; j <= m; j++)
if (best[j-len] + pts > best[j])
best[j] = best[j-len] + pts;
}
fout << best[m] << endl; // 由於數組元素不減,末元素最大
}
USACO 3.3
A Game
題目如下:
有如下一個雙人遊戲:N(2 <= N <= 100)個正整數的序列放在一個遊戲平台上,兩人輪流從序列的兩端取數,取數后該數字被去掉並累加到本玩家的得分中,當數取盡時,遊戲結束。以最終得分多者為勝。
編一個執行最優策略的程序,最優策略就是使自己能得到在當前情況下最大的可能的總分的策略。你的程序要始終為第二位玩家執行最優策略。
PROGRAM NAME: game1
INPUT FORMAT
第一行: 正整數N, 表示序列中正整數的個數。
第二行至末尾: 用空格分隔的N個正整數(大小為1-200)。
SAMPLE INPUT (file game1.in)
6
4 7 2 9
5 2
OUTPUT FORMAT
只有一行,用空格分隔的兩個整數: 依次為玩家一和玩家二最終的得分。
SAMPLE OUTPUT (file game1.out)
18 11
參考程序如下:
#include <stdio.h>
#define NMAX 101
int best[NMAX][2], t[NMAX];
int n;
void
readx () {
int i, aux;
freopen ("game1.in", "r", stdin);
scanf ("%d", &n);
for (i = 1; i <= n; i++) {
scanf ("%d", &aux);
t= t[i - 1] + aux;
}
fclose (stdin);
}
inline int
min (int x, int y) {
return x > y ? y : x;
}
void
solve () {
int i, l;
for (l = 1; l <= n; l++)
for (i = 1; i + l <= n + 1; i++)
best[l%2] = t[i + l - 1] - t[i - 1] - min (best[i + 1][(l - 1) % 2],
best[(l - 1) % 2]);
}
void writex () {
freopen ("game1.out", "w", stdout);
printf ("%d %d\n", best[1][n % 2], t[n] - best[1][n % 2]);
fclose (stdout);
}
int
main () {
readx ();
solve ();
writex ();
return 0;
}
USACO 3.4
Raucous Rockers
題目如下:
你剛剛得到了流行的「破鑼搖滾」樂隊錄製的尚未發表的N(1 <= N <= 20)首歌的版權。你打算從中精選一些歌曲,發行M(1 <= M <= 20)張CD。每一張CD最多可以容納T(1 <= T <= 20)分鐘的音樂,一首歌不能分裝在兩張CD中。
不巧你是一位古典音樂迷,不懂如何判定這些歌的藝術價值。於是你決定根據以下標準進行選擇:
歌曲必須按照創作的時間順序在CD盤上出現。
選中的歌曲數目儘可能地多。
PROGRAM NAME: rockers
INPUT FORMAT
第一行: 三個整數:N, T, M.
第二行: N個整數,分別表示每首歌的長度,按創作時間順序排列。
SAMPLE INPUT (file rockers.in)
4 5 2
4 3 4 2
OUTPUT FORMAT
一個整數,表示可以裝進M張CD盤的樂曲的最大數目。
SAMPLE OUTPUT (file rockers.out)
3
參考程序如下:
#include <stdio.h>
#define MAX 25
int dp[MAX][MAX][MAX], length[MAX];
int
main ()
{
FILE *in = fopen ("rockers.in", "r");
FILE *out = fopen ("rockers.out", "w");
int a, b, c, d, best, numsongs, cdlength, numcds;
fscanf (in, "%d%d%d", &numsongs, &cdlength, &numcds);
for (a = 1; a <= numsongs; a++)
fscanf (in, "%d", &length[a]);
best = 0;
for (a = 0; a < numcds; a++)"
for (b = 0; b <= cdlength; b++) "
for (c = 0; c <= numsongs; c++) { "
for (d = c + 1; d <= numsongs; d++) { "
if (b + length[d] <= cdlength) {
if (dp[a][c] + 1 > dp[a][b + length[d]][d])
dp[a][b + length[d]][d] = dp[a][c] + 1;
}
else {
if (dp[a][c] + 1 > dp[a + 1][length[d]][d])
dp[a + 1][length[d]][d] = dp[a][c] + 1;
}
}
if (dp[a][c] > best)
best = dp[a][c];
}
fprintf (out, "%d\n", best);
return 0;
}
USACO
4.3 Buy Low, Buy Lower
「逢低吸納」是炒股的一條成功秘訣。如果你想成為一個成功的投資者,就要遵守這條秘訣:
"逢低吸納,越低越買"
這句話的意思是:每次你購買股票時的股價一定要比你上次購買時的股價低.按照這個規則購買股票的次數越多越好,看看你最多能按這個規則買幾次。
逢低吸納,越低越買

  逢低吸納,越低越買

給定連續的N天中每天的股價。你可以在任何一天購買一次股票,但是購買時的股價一定要比你上次購買時的股價低。寫一個程序,求出最多能買幾次股票。
以下面這個表為例, 某幾天的股價是:
天數 1 2 3 4 5 6 7 8 9 10 11 12
股價 68 69 54 64 68 64 70 67 78 62 98 87
這個例子中, 聰明的投資者(按上面的定義),如果每次買股票時的股價都比上一次買時低,那麼他最多能買4次股票。一種買法如下(可能有其他的買法):
天數 2 5 6 10
股價 69 68 64 62
PROGRAM NAME: buylow
INPUT FORMAT
第1行: N (1 <= N <= 5000), 表示能買股票的天數。
第2行以下: N個正整數 (可能分多行) ,第i個正整數表示第i天的股價. 這些正整數大小不會超過longint(pascal)/long(c++).
SAMPLE INPUT (file buylow.in)
12
68 69 54 64 68 64 70 67
78 62 98 87
OUTPUT FORMAT
只有一行,輸出兩個整數:
能夠買進股票的天數
長度達到這個值的股票購買方案數量
在計算解的數量的時候,如果兩個解所組成的字元串相同,那麼這樣的兩個解被認為是相同的(只能算做一個解)。因此,兩個不同的購買方案可能產生同一個字元串,這樣只能計算一次。
SAMPLE OUTPUT (file buylow.out)
4 2
參考程序如下:
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef struct BIGNUM *bignum_t;
struct BIGNUM
{
int val;
bignum_t next;
};
int num[5000];
int len[5000];
int nlen;
bignum_t cnt[5000];
bignum_t get_big(void)
{
static bignum_t block;
static int size = 0;
if (size == 0)
{
block = (bignum_t)malloc(sizeof(*block)*128);
size = 128;
}
size--;
return block++;
}
"
void init_big(bignum_t *num, int val)
{
*num = get_big();
"
(*num)->val = val;
(*num)->next = NULL;
}
void add(bignum_t a, bignum_t b)
{
int c; "
c = 0;
while (b || c)
{
a->val += c;
if (b) a->val += b->val;
"
c = (a->val / 1000000);
a->val = (a->val % 1000000);
if (b) b = b->next;
if (!a->next && (b || c))
{ "
a->next = get_big();
a = a->next;
a->val = 0;
a->next = NULL;
} else a = a->next;
}
}
void out_num(FILE *f, bignum_t v)
{
if (v->next)
{
out_num(f, v->next);
fprintf (f, "%06i", v->val);
}
else
fprintf (f, "%i", v->val);
}
int main(int argc, char **argv)
{
FILE *fout, *fin;
int lv, lv2;
int c;
int max;
int l;
bignum_t ans;
if ((fin = fopen("buylow.in", "r")) == NULL)
{
perror ("fopen fin");
exit(1);
}
if ((fout = fopen("buylow.out", "w")) == NULL)
{
perror ("fopen fout");
exit(1);
}
fscanf (fin, "%d", &nlen);
for (lv = 0; lv < nlen; lv++)
fscanf (fin, "%d", &num[lv]);
"
for (lv = 0; lv < nlen; lv++)
{
max = 1;
for (lv2 = lv-1; lv2 >= 0; lv2--)
if (num[lv2] > num[lv] && len[lv2]+1 > max) max = len[lv2]+1;
len[lv] = max;
}
for (lv = 0; lv < nlen; lv++)
{
if (len[lv] == 1) init_big(&cnt[lv], 1);
else
{
init_big(&cnt[lv], 0);
l = -1;
max = len[lv]-1;
for (lv2 = lv-1; lv2 >= 0; lv2--)
if (len[lv2] == max && num[lv2] > num[lv] && num[lv2] != l)
add(cnt[lv], cnt[lv2]);
l = num[lv2];
}
}
}
"
max = 0;
for (lv = 0; lv < nlen; lv++)
if (len[lv] > max) max = len[lv];
init_big(&ans, 0);
l = -1;
for (lv = nlen-1; lv >= 0; lv--)
if (len[lv] == max && num[lv] != l)
{
add(ans, cnt[lv]);
l = num[lv];
}
"
fprintf (fout, "%i ", max);
out_num(fout, ans);
fprintf (fout, "\n");
return 0;
}
動態規劃作為一種重要的信息學競賽演算法,具有很強的靈活性。以上提供的是一些入門練習題,深入的學習還需要逐步積累經驗。

12書籍

《Dynamic Programming》
ISBN:3540370137
出版日期】 2005 年7月 【頁 碼】 379
目錄
引言
動態規劃的基本概念
動態規劃的基本定理和基本方程
動態規劃的適用條件
動態規劃的基本思想
動態規劃的基本步驟
動態規劃的實例分析
動態規劃的技巧
動態規劃實現中的問題
動態規劃與其他演算法的比較
動態規劃的理論基礎
其他資料

13程序實現

解決0-1背包問題時使用動態規劃的實現(c++)
#include <stdio.h>
typedef struct Object
{
int weight;
int value;
// float rate;
}Object;
Object * array; //用來存儲物體信息的數組
int num; //物體的個數
int container; //背包的容量
int ** dynamic_table; //存儲動態規劃表
bool * used_table; //存儲物品的使用情況
//ouput the table of dynamic programming, it's for detection
void print_dynamic_table()
{
printf("動態規劃表如下所示:\n");
"
for(int i=1; i<=num; i++)
{
for(int j=0; j<=container; j++)
printf("%d ",dynamic_table[i][j]);
printf("\n");
}
}
//列印動態規劃表
void print_array()
{
for(int i=1; i<=num; i++)
printf("第%d個物品的重量和權重:%d %d\n",i,array[i].weight,array[i].value);
}
//列印輸入的物品情況
//插入排序,按rate=value/weight由小到大排
//動態規劃考慮了所有情況,所以可以不用排序
"
void print_used_object()
{
printf("所使用的物品如下所示:\n");
for(int i=1; i<=num; i++)
if(used_table[i]==1)
printf("%d-%d\n", array[i].weight, array[i].value);
}
//列印物品的使用情況
/* 做測試時使用
void print_used_table(bool * used_table)
{
printf("used table as follows:\n");
for(int i=1; i<=num; i++)
printf("object %d is %d", i, used_table[i]);
}
*/
void init_problem()
{
printf("輸入背包的容量:\n");
scanf("%d", &container);
printf("輸入物品的個數:\n");
scanf("%d", &num);
array=new Object[num+1];
printf("輸入物品的重量和價值, 格式如:4-15\n");
for(int i=1; i<=num; i++)
{
char c;
scanf("%d%c%d", &array[i].weight, &c, &array[i].value);
// array[i].rate=array[i].value/array[i].weight;
}
print_array();
}
//對物體的使用情況進行回查
void trace_back()
{
int weight=container;
used_table=new bool[num+1];
for(int i=1; i<=num; i++)
used_table[i]=0;
//initalize the used_table to be non-used
for(int j=1; j<num; j++)
{
//說明物品j被使用
if(dynamic_table[j][weight]!=dynamic_table[j+1][weight])
{
weight-=array[j].weight;
used_table[j]=1;
}
// print_used_table(used_table);
}
//檢測第num個物品是否被使用
if(weight>=array[num].weight)
used_table[num]=1;
}
void dynamic_programming()
{
dynamic_table=new int * [num+1];
for(int k=1; k<=num; k++)
dynamic_table[k]=new int[container+1]; //dynamic_programming table
//為二維動態規劃表分配內存
for(int m=1; m<num; m++)
for(int n=0; n<=container; n++)
dynamic_table[m][n]=0;
int temp_weight=array[num].weight;
for(int i=0; i<=container; i++)
dynamic_table[num][i]=i<temp_weight?0:array[num].value;
//初始化動態規劃表
for(int j=num-1; j>=1; j--)
{
temp_weight=array[j].weight;
int temp_value=array[j].value;
for(int k=0; k<=container; k++)
if(k>=temp_weight && dynamic_table[j+1][k] < dynamic_table[j+1][k-temp_weight]+temp_value)
dynamic_table[j][k]=dynamic_table[j+1][k-temp_weight]+temp_value;
else
dynamic_table[j][k]=dynamic_table[j+1][k];
}
//構建動態規劃表
print_dynamic_table();
//列印動態規劃表
}
void main()
{
init_problem();
dynamic_programming();
trace_back();
print_used_object();
}

相關評論

同義詞:暫無同義詞