0.關于
動態規劃是編程解題的一種重要手段，1951 年美國數學家 R.Bellman 等人，根據一類多階段問題的特點，把多階段決策問題變換為一系列互相聯系的單階段問題，然后逐個加以解決，與此同時，他提出了解決這類問題的“最優化原理”，從而創建了解決最優化問題的一種新方法：動態規劃，
動態規劃演算法通常用于求解具有某種最優性質的問題，在這類問題中，可能會有許多可行解，每一個解都對應于一個值，我們希望找到具有最優值的解，
我們可以用一個表來記錄所有已解的子問題的答案，不管該子問題以后是否被用到，只要它被計算過，就將其結果填入表中，這就是動態規劃法的基本思路，具體的動態規劃演算法多種多樣，但它們具有相同的填表格式，
1.基本概念
· 階段：把所給問題的求解程序恰當地分成若干個相互聯系的階段，以便于求解，程序不同，階段數就可能不同，描述階段的變數稱為階段變數，常用 k 表示，階段的劃分，一般是根據時間和空間的自然特征來劃分，但要便于把問題的程序轉化為多階段決策的程序，
· 狀態：狀態表示每個階段開始面臨的自然狀況或客觀條件，它不以人們的主觀意志為轉移，也稱為不可控因素，通常一個階段有若干個狀態，狀態通常可以用一個或一組數來描述，稱為狀態變數，
· 決策：表示當程序處于某一階段的某個狀態時，可以做出不同的決定，從而確定下一階段的狀態，這種決定稱為決策，不同的決策對應著不同的數值，描述決策的變數稱決策變數，
· 狀態轉移方程：動態規劃中本階段的狀態往往是上一階段的狀態和上一階段的決策的結果，由第 i 段的狀態 f(i) ,和決策 u(i) 來確定第 i+1 段的狀態，狀態轉移表示為 F(i+1) = T(f(i),u(i)) ，稱為狀態轉移方程，
· 策略：各個階段決策確定后，整個問題的決策序列就構成了一個策略，對每個實際問題，可供選擇的策略有一定范圍，稱為允許策略集合，允許策略集合中達到最優效果的策略稱為最優策略，
動態規劃必須滿足最優化原理與無后效性，
· 最優化原理：“一個程序的最優決策具有這樣的性質：即無論其初始狀態和初始決策如何，其今后諸策略對以第一個決策所形成的狀態作為初始狀態的程序而言，必須構成最優策略”，也就是說一個最優策略的子策略，也是最優的，
· 無后效性：如果某階段狀態給定后，則在這個階段以后程序的發展不受這個階段以前各個狀態的影響，
舉個栗子
來看一道題目，
可憐的可樂機要回家，已知小可樂機在 左下角 (1,1) 位置，家在 右上角 (n,n) 坐標處，小可樂機走上一個格子 (i,j) 會花費一定的體力 a[i][j]，而且小可樂機只會往家的方向走，也就是只能往上，或者往右走，小可樂機想知道他回到家需要花費的最少體力是多少, 求你幫幫小可樂機吧qwq
例如下圖所示，格子中的數字代表走上該格子花費的體力：
對于該圖來說，最優策略已在圖上標出，最少花費體力為：3 + 2 + 4 + 3 = 123 + 2 + 4 + 3 = 12，
我們把走到一個點看做一個狀態，對小可樂機來說，走到一個點只有兩種方式，一個是從下面走到該點，一種是從左邊走到該點，那么點 (i,j) 要么是從 (i-1,j) 走到 (i,j)，要么是從點 (i,j-1) 走到 (i,j)，
所以從哪個點走到 (i,j) 就是一個 決策，接下來，我們用 dp(i,j) 來代表走到點 (i,j) 一共花費的最少體力，
我們需要花費最少力氣走到家，所以可以得到狀態轉移方程：dp(i,j) = min(dp(i-1,j), dp(i,j-1)) + a[i][j] ，根據轉移方程，我們可以推出走到每個點花費的最少體力，
對于圖中的邊界點，要在轉移前加上判斷是否為邊界，如：點 (1,3) 只能從點 (1,2) 走過來，點 (3,1) 只能從點 (2,1) 走過來等等，
動態規劃的題目的核心是寫出狀態轉移方程，對于一個動態規劃的題目，如果我們能寫出轉移方程那么代碼實作就變得簡單多了，大部分的動態規劃題目，在計算出轉移方程后，可以用類似于遞推的回圈結構，來寫出代碼，
主要代碼
int a[100][100]; // a陣列代表在點(i,j)花費的體力
int dp[100][100]; // dp陣列代表走到點(i,j)一共花費的最少體力
dp[1][1] = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (i == 1 && j == 1)
{
continue;
}
else if (i == 1) //邊界點
{
dp[i][j] = dp[i][j-1] + a[i][j];
}
else if (j == 1) //邊界點
{
dp[i][j] = dp[i-1][j] + a[i][j];
}
else
{
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + a[i][j]; //轉移方程
}
}
}
01背包
01背包的主要思路是從后往前一次看當前這個物品選不選
那么有：
如果剩下的容量裝不下這個物品：\(dp(i,j)=dp(i-1,j)\) (表示不選)
否則有 \(dp(i,j)=max(dp(i-1,j),dp(i-1,j-w_i)+v_i)\)
// 通過記憶化搜索實作的代碼
#include <bits/stdc++.h>
#define MAXN 4005
#define MAXW 5005
using namespace std;
int n, W, w[MAXN], v[MAXN], dp[MAXN][MAXW];
int solve(int n, int W) // first n items. weight W
{
if(n == 0) // 如果沒有物品了，那么就肯定得不到任何價值了，所以在這里return 0（邊界條件）
return 0;
if(dp[n][W] != -1)
return dp[n][W];
if(W < w[n])
return solve(n - 1, W);
else
return max(solve(n - 1, W), solve(n - 1, W - w[n]) + V[n]);
}
int main()
{
memset(dp, -1, sizeof(dp));
scanf("%d %d", &n, &W);
for(int i = 1; i <= n; i++)
scanf("%d %d", &w[i], &v[i]);
printf("%d\n", solve(n, W));
return 0;
}
// 通過DP實作的代碼
#include <bits/stdc++.h>
#define MAXN 4005
#define MAXW 5005
using namespace std;
int n, W, w[MAXN], v[MAXN], dp[MAXN][MAXW];
int main()
{
memset(dp, -1, sizeof(dp));
scanf("%d %d", &n, &W);
for(int i = 1; i <= n; i++)
scanf("%d %d", &w[i], &v[i]);
for(int i = 1; i <= n; i++)
for(int j = 0; j <= W; j++)
{
if(j < W[i])
dp[i][j]=dp[i-1][j];
else
dp[i][j]=max(dp[i-1][j]), dp([i-1][j-w[i]])+v[i]);
}
cout << dp[n][W] << endl;
return 0;
}
空間優化
我們仔細看這個01背包的遞推式：
\(
dp[i][j]=
\left\{
\begin{array}{**lr**}
dp[i-1][j], & j<w[i]\\
max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]) &
\end{array}
\right.
\)
可以發現dp[i][j]至于dp[i-1][多少多少]有關系，所以可以只用兩行就可以存下來，
于是空間就只需要\(O(2*W)\)啦
#include <bits/stdc++.h>
#define MAXN 4005
#define MAXW 5005
using namespace std;
int n, W, w[MAXN], v[MAXN], dp[2][MAXW];
int main()
{
scanf("%d %d", &W, &n);
for(int i = 1; i <= n; i++)
scanf("%d %d", &w[i], &v[i]);
for(int i = 1; i <= n; i++)
for(int j = 0; j <= W; j++)
{
if(j < w[i])
dp[i%2][j]=dp[(i-1)%2][j];
else
dp[i%2][j]=max(dp[(i-1)%2][j], dp[(i-1)%2][j-w[i]]+v[i]);
}
cout << dp[n%2][W] << endl;
return 0;
}
最長不下降子序列
給你一個序列，讓你求其中最長不下降子序列的長度[1]；
仔細思考一下，我們想出來一個狀態轉移方程：
\[dp[i]=max(dp[i],dp[j]+1) \text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ } 1\leq j \leq n 且 a[i] >= a[j] \]
那代碼就是這樣寫的啦：
#include <bits/stdc++.h>
using namespace std;
#define MAXN 10005
int a[MAXN], dp[MAXN];
int main()
{
memset(dp, 0, sizeof(dp));
int N;
scanf("%d", &N);
for(int i = 1; i <= N; i++)
scanf("%d", &a[i]);
for(int i = 1; i <= N; i++)
{
dp[i] = 1;
for(int j = 1; j < i; j++)
if(a[i] >= a[j])
dp[i] = max(dp[i], dp[j] + 1);
}
int ans = 0;
for(int i = 1; i <= N; i++)
ans = max(ans, dp[i]);
cout << ans << endl;
return 0;
}
一個序列，滿足 \(a[i]>=a[j] \text{ }\text{ }\text{ }\text{ }\text{ } 1 \leq j \leq n\) ??
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/77553.html
標籤：C++
上一篇：關于讀取TXT檔案的問題，求大神
下一篇：dfs