最近在看關(guān)于數(shù)據(jù)結(jié)構(gòu)系列知識(shí)點(diǎn)贫堰，然后遇到一個(gè)動(dòng)態(tài)規(guī)劃相關(guān)的題目——郵票規(guī)劃坤按。
首先先介紹下關(guān)于DPS弃衍，也就是深度優(yōu)先遍歷算法吧惊豺。
深度優(yōu)先遍歷
深度優(yōu)先遍歷燎孟，從初始訪問(wèn)結(jié)點(diǎn)出發(fā)，我們知道初始訪問(wèn)結(jié)點(diǎn)可能有多個(gè)鄰接結(jié)點(diǎn)扮叨，深度優(yōu)先遍歷的策略就是首先訪問(wèn)第一個(gè)鄰接結(jié)點(diǎn)缤弦，然后再以這個(gè)被訪問(wèn)的鄰接結(jié)點(diǎn)作為初始結(jié)點(diǎn)，訪問(wèn)它的第一個(gè)鄰接結(jié)點(diǎn)彻磁“澹總結(jié)起來(lái)可以這樣說(shuō)：每次都在訪問(wèn)完當(dāng)前結(jié)點(diǎn)后首先訪問(wèn)當(dāng)前結(jié)點(diǎn)的第一個(gè)鄰接結(jié)點(diǎn)。
一句話的事情：優(yōu)先進(jìn)行縱向訪問(wèn)衷蜓，而不是廣度優(yōu)先遍歷的橫向進(jìn)行訪問(wèn)
動(dòng)態(tài)規(guī)劃相關(guān)知識(shí)點(diǎn)
動(dòng)態(tài)規(guī)劃算法的基本思想是：將帶求解的問(wèn)題分解成若干個(gè)相互聯(lián)系的子問(wèn)題累提，先求解子問(wèn)題，然后從這些子問(wèn)題的解中得到原問(wèn)題的解磁浇；對(duì)于重復(fù)出現(xiàn)的子問(wèn)題斋陪，只在第一次遇到的時(shí)候?qū)λM(jìn)行求解，并把答案保存起來(lái)，避免重復(fù)求解无虚。該思想與記憶化搜索類似缔赠，即將計(jì)算步驟中的過(guò)程保存下來(lái)，避免重復(fù)運(yùn)算
要點(diǎn)：
- 動(dòng)態(tài)規(guī)劃適用于這些子問(wèn)題不是獨(dú)立的情況友题，也就是各子問(wèn)題包含公共子問(wèn)題
- 需要記錄每個(gè)子問(wèn)題求解的問(wèn)題結(jié)果嗤堰，以供其他問(wèn)題進(jìn)行解決
相關(guān)步驟
- 劃分階段：按照問(wèn)題的時(shí)間或空間特征，把問(wèn)題分為若干個(gè)階段度宦。在劃分階段時(shí)踢匣，注意劃分后的階段一定要是有序的或者是可排序的，否則問(wèn)題就無(wú)法求解戈抄。
- 確定狀態(tài)和狀態(tài)變量：注意狀態(tài)必須滿足無(wú)后效性离唬。
- 確定決策：找到子問(wèn)題是進(jìn)行動(dòng)態(tài)規(guī)劃的重要一步。動(dòng)態(tài)規(guī)劃和遞推更多應(yīng)考慮本問(wèn)題由哪些已解決子問(wèn)題構(gòu)成划鸽，而不是考慮本問(wèn)題對(duì)將來(lái)哪些問(wèn)題有貢獻(xiàn)输莺。
- 確定邊界條件，寫(xiě)出狀態(tài)轉(zhuǎn)移方程
具體事例
問(wèn)題描述
給定一個(gè)信封裸诽，最多只允許粘貼N張郵票模闲，計(jì)算在給定K（N+K≤13）種郵票的情況下（假定所有的郵票數(shù)量都足夠），如何設(shè)計(jì)郵票的面值崭捍，能得到最大值MAX尸折，使在1～MAX之間的每一個(gè)郵資值都能得到。
例如殷蛇，N=3实夹，K=2，如果面值分別為1分粒梦、4分亮航，則在1分～6分之間的每一個(gè)郵資值都能得到（當(dāng)然還有8分、9分和12分）匀们；如果面值分別為1分缴淋、3分，則在1分～7分之間的每一個(gè)郵資值都能得到泄朴≈囟叮可以驗(yàn)證當(dāng)N=3，K=2時(shí)祖灰，7分就是可以得到的連續(xù)的郵資最大值钟沛，所以MAX=7，面值分別為1分局扶、3分恨统。
輸入格式
一行叁扫，兩個(gè)數(shù)N、K
輸出格式
兩行畜埋，第一行升序輸出設(shè)計(jì)的郵票面值莫绣，第二行輸出“MAX=xx”（不含引號(hào)），其中xx為所求的能得到的連續(xù)郵資最大值悠鞍。
樣例輸入
3 2
樣例輸出
1 3
MAX=7
當(dāng)看到這個(gè)問(wèn)題我們藉由之前的理論來(lái)具體分析下兔综。
動(dòng)態(tài)規(guī)劃
- 子問(wèn)題
- 是否選擇面值各大的郵票呢，這里顯示選擇只能“是”或者“否”
- 最優(yōu)子結(jié)構(gòu)
- 當(dāng)然同理狞玛，連續(xù)郵票的面值在每個(gè)值下都成立，這樣就構(gòu)成了結(jié)構(gòu)涧窒。
- 邊界
郵票的種類數(shù)目
當(dāng)然有了上面的幾點(diǎn)心肪，我們?cè)囍鴮?xiě)下該方式的轉(zhuǎn)化方程，假如n代表郵票總共類別纠吴，i代表郵票總面值硬鞍，stamp[i]代表郵票所屬值大小，dp[i]代表湊齊 i 面值最少需要多少郵票戴已，Dp(int position)代表幾種類別的所能組成郵票值固该。
- 當(dāng)i >= stamp[k] && dp[i] > dp[i - stamp[k]] + 1，則 dp[i] = dp[i - stamp[k]] + 1;就是說(shuō)取最大的那個(gè)糖儡。
- 當(dāng)dp[i]>n伐坏，Dp(position)=i,
- 當(dāng)dp[i]<n,Dp(postion)=-1;就是說(shuō)無(wú)意義
DPS的使用
- deep深度——由于每個(gè)郵件的類別數(shù)目難以確定，所以需要以郵票數(shù)目為DPS的遞歸深度deep）
- 中止條件——當(dāng)確定最大連續(xù)能取得值maxm握联，那么新加入的物品價(jià)值一旦大于maxm+1桦沉，顯然就會(huì)出現(xiàn)斷層，所以可以以maxm+1為枚舉上界金闽，然后這樣進(jìn)行下一層的dfs纯露。
附上java代碼：
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int N=500;
static int n,m,ans;
static int a[]=new int[N+1];
static int b[]=new int[N+1];
static int f[]=new int[N+1];
public static void main(String[] args) {
int i,j,k;
Scanner scanner =new Scanner(System.in);
n=scanner.nextInt();
m=scanner.nextInt();
a[1]=1;
dfs(1);
for(i=1;i<=m;i++)
System.out.printf("%d ",b[i]);
System.out.printf("\nMAX=%d\n",ans);
}
static void dfs(int deep)
{
int i,j,uplimit;
Arrays.fill(f,0x3f);
f[0]=0;
for(uplimit=1;uplimit<=N;uplimit++)
{
for(i=1;i<=deep&&a[i]<=uplimit;i++)
f[uplimit]=Math.min(f[uplimit],f[uplimit-a[i]]+1);
if(f[uplimit]>n)
{
uplimit--;
if(uplimit>ans)
{
ans=uplimit;
for(i=1;i<=deep;i++)
b[i]=a[i];
}
break;
}
}
if(deep==m)return ;
for(i=uplimit+1;i>a[deep];i--)
{
a[deep+1]=i;
dfs(deep+1);
}
}
}
