Ⅰ 怎樣用動態規劃演算法解決24點問題，稍詳細些，謝謝
枚舉法： Enumeration
排序：Sort
貪心法：Greedy algorithm
遞歸：Recursion
分治：Divide and Rule
深度優先搜索：Depth First Search(DFS)
寬(廣)度優先搜索：Breadth First Search(BFS)
動態規劃：Dynamic Programming(DP) 也有人叫它 Dynamic Process
離散化：Discretization
棧：Stack Last in First out (LIFO)
隊列：Queue First in First out(FIFO)
順序表：Array Array-Based List
鏈表：Chain Linked List
廣義表：Lists
串：String
集合：Set
樹：Tree
二叉樹：Binary Tree
完全二叉樹：Complete Binary Tree
二叉搜索樹：Binary Search Tree(BST)
堆：Heap
圖：Graph
哈希表：Hash Table
並查集：Union-Find Sets 或 Disjoint Sets
最大匹配：maximal matching
線段樹：Segment Tree
樹狀數組：Binary Indexed Tree
伸展樹：Splay Tree
左偏樹：Leftist Tree 或 Leftist Heap
斐波那契堆：Fibonacci Heap
後綴樹：Suffix Tree
網路流：Network Flows
凸包：Convex Hull
叉積：Cross Function
高斯消元：Gaussian Elimination
匹配：Matching
矩陣：Matrix
Ⅱ 0-1背包問題的多種解法代碼（動態規劃、貪心法、回溯法、分支限界法）
一.動態規劃求解0-1背包問題
/************************************************************************/
/* 0-1背包問題：
/* 給定n種物品和一個背包
/* 物品i的重量為wi，其價值為vi
/* 背包的容量為c
/* 應如何選擇裝入背包的物品，使得裝入背包中的物品
/* 的總價值最大？
/* 註：在選擇裝入背包的物品時，對物品i只有兩種選擇，
/* 即裝入或不裝入背包。不能將物品i裝入多次，也
/* 不能只裝入部分的物品i。
/*
/* 1. 0-1背包問題的形式化描述：
/* 給定c>0, wi>0, vi>0, 0<=i<=n，要求找到一個n元的
/* 0-1向量(x1, x2, ..., xn), 使得：
/* max sum_{i=1 to n} (vi*xi),且滿足如下約束：
/* (1) sum_{i=1 to n} (wi*xi) <= c
/* (2) xi∈{0, 1}, 1<=i<=n
/*
/* 2. 0-1背包問題的求解
/* 0-1背包問題具有最優子結構性質和子問題重疊性質，適於
/* 採用動態規劃方法求解
/*
/* 2.1 最優子結構性質
/* 設(y1,y2,...,yn)是給定0-1背包問題的一個最優解，則必有
/* 結論，(y2,y3,...,yn)是如下子問題的一個最優解：
/* max sum_{i=2 to n} (vi*xi)
/* (1) sum_{i=2 to n} (wi*xi) <= c - w1*y1
/* (2) xi∈{0, 1}, 2<=i<=n
/* 因為如若不然，則該子問題存在一個最優解(z2,z3,...,zn)，
/* 而(y2,y3,...,yn)不是其最優解。那麼有：
/* sum_{i=2 to n} (vi*zi) > sum_{i=2 to n} (vi*yi)
/* 且，w1*y1 + sum_{i=2 to n} (wi*zi) <= c
/* 進一步有：
/* v1*y1 + sum_{i=2 to n} (vi*zi) > sum_{i=1 to n} (vi*yi)
/* w1*y1 + sum_{i=2 to n} (wi*zi) <= c
/* 這說明：(y1,z2,z3,...zn)是所給0-1背包問題的更優解，那麼
/* 說明(y1,y2,...,yn)不是問題的最優解，與前提矛盾，所以最優
/* 子結構性質成立。
/*
/* 2.2 子問題重疊性質
/* 設所給0-1背包問題的子問題 P(i,j)為：
/* max sum_{k=i to n} (vk*xk)
/* (1) sum_{k=i to n} (wk*xk) <= j
/* (2) xk∈{0, 1}, i<=k<=n
/* 問題P(i,j)是背包容量為j、可選物品為i,i+1,...,n時的子問題
/* 設m(i,j)是子問題P(i,j)的最優值，即最大總價值。則根據最優
/* 子結構性質，可以建立m(i,j)的遞歸式：
/* a. 遞歸初始 m(n,j)
/* //背包容量為j、可選物品只有n，若背包容量j大於物品n的
/* //重量，則直接裝入；否則無法裝入。
/* m(n,j) = vn, j>=wn
/* m(n,j) = 0, 0<=j<wn
/* b. 遞歸式 m(i,j)
/* //背包容量為j、可選物品為i,i+1,...,n
/* //如果背包容量j<wi，則根本裝不進物品i，所以有：
/* m(i,j) = m(i+1,j), 0<=j<wi
/* //如果j>=wi，則在不裝物品i和裝入物品i之間做出選擇
/* 不裝物品i的最優值：m(i+1,j)
/* 裝入物品i的最優值：m(i+1, j-wi) + vi
/* 所以：
/* m(i,j) = max {m(i+1,j), m(i+1, j-wi) + vi}, j>=wi
/*
/************************************************************************/
#define max(a,b) (((a) > (b)) ? (a) : (b))
#define min(a,b) (((a) < (b)) ? (a) : (b))
template <typename Type>
void Knapsack(Type* v, int *w, int c, int n, Type **m)
{
//遞歸初始條件
int jMax = min(w[n] - 1, c);
for (int j=0; j<=jMax; j++) {
m[n][j] = 0;
}
for (j=w[n]; j<=c; j++) {
m[n][j] = v[n];
}
//i從2到n-1，分別對j>=wi和0<=j<wi即使m(i,j)
for (int i=n-1; i>1; i--) {
jMax = min(w[i] - 1, c);
for (int j=0; j<=jMax; j++) {
m[i][j] = m[i+1][j];
}
for (j=w[i]; j<=c; j++) {
m[i][j] = max(m[i+1][j], m[i+1][j-w[i]]+v[i]);
}
}
m[1][c] = m[2][c];
if (c >= w[1]) {
m[1][c] = max(m[1][c], m[2][c-w[1]]+v[1]);
}
}
template <typename Type>
void TraceBack(Type **m, int *w, int c, int n, int* x)
{
for (int i=1; i<n; i++) {
if(m[i][c] == m[i+1][c]) x[i] = 0;
else {
x[i] = 1;
c -= w[i];
}
}
x[n] = (m[n][c])? 1:0;
}
int main(int argc, char* argv[])
{
int n = 5;
int w[6] = {-1, 2, 2, 6, 5, 4};
int v[6] = {-1, 6, 3, 5, 4, 6};
int c = 10;
int **ppm = new int*[n+1];
for (int i=0; i<n+1; i++) {
ppm[i] = new int[c+1];
}
int x[6];
Knapsack<int>(v, w, c, n, ppm);
TraceBack<int>(ppm, w, c, n, x);
return 0;
}
二.貪心演算法求解0-1背包問題
1.貪心法的基本思路：
——從問題的某一個初始解出發逐步逼近給定的目標，以盡可能快的地求得更好的解。當達到某演算法中的某一步不能再繼續前進時，演算法停止。
該演算法存在問題：
1).不能保證求得的最後解是最佳的；
2).不能用來求最大或最小解問題；
3).只能求滿足某些約束條件的可行解的范圍。
實現該演算法的過程：
從問題的某一初始解出發；
while 能朝給定總目標前進一步 do
求出可行解的一個解元素；
由所有解元素組合成問題的一個可行解；
2.例題分析
1).[背包問題]有一個背包，背包容量是M=150。有7個物品，物品可以分割成任意大小。
要求盡可能讓裝入背包中的物品總價值最大，但不能超過總容量。
物品 A B C D E F G
重量 35 30 60 50 40 10 25
價值 10 40 30 50 35 40 30
分析：
目標函數： ∑pi最大
約束條件是裝入的物品總重量不超過背包容量：∑wi<=M( M=150)
（1）根據貪心的策略，每次挑選價值最大的物品裝入背包，得到的結果是否最優？
（2）每次挑選所佔空間最小的物品裝入是否能得到最優解？
（3）每次選取單位容量價值最大的物品，成為解本題的策略。
<程序代碼:>(環境:c++)
#include<iostream.h>
#define max 100 //最多物品數
void sort (int n,float a[max],float b[max]) //按價值密度排序
{
int j,h,k;
float t1,t2,t3,c[max];
for(k=1;k<=n;k++)
c[k]=a[k]/b[k];
for(h=1;h<n;h++)
for(j=1;j<=n-h;j++)
if(c[j]<c[j+1])
{t1=a[j];a[j]=a[j+1];a[j+1]=t1;
t2=b[j];b[j]=b[j+1];b[j+1]=t2;
t3=c[j];c[j]=c[j+1];c[j+1]=t3;
}
}
void knapsack(int n,float limitw,float v[max],float w[max],int x[max])
{float c1; //c1為背包剩餘可裝載重量
int i;
sort(n,v,w); //物品按價值密度排序
c1=limitw;
for(i=1;i<=n;i++)
{
if(w[i]>c1)break;
x[i]=1; //x[i]為1時，物品i在解中
c1=c1-w[i];
}
}
void main()
{int n,i,x[max];
float v[max],w[max],totalv=0,totalw=0,limitw;
cout<<"請輸入n和limitw:";
cin>>n >>limitw;
for(i=1;i<=n;i++)
x[i]=0; //物品選擇情況表初始化為0
cout<<"請依次輸入物品的價值："<<endl;
for(i=1;i<=n;i++)
cin>>v[i];
cout<<endl;
cout<<"請依次輸入物品的重量："<<endl;
for(i=1;i<=n;i++)
cin>>w[i];
cout<<endl;
knapsack (n,limitw,v,w,x);
cout<<"the selection is:";
for(i=1;i<=n;i++)
{
cout<<x[i];
if(x[i]==1)
totalw=totalw+w[i];
}
cout<<endl;
cout<<"背包的總重量為："<<totalw<<endl; //背包所裝載總重量
cout<<"背包的總價值為："<<totalv<<endl; //背包的總價值
}
三.回溯演算法求解0-1背包問題
1.0-l背包問題是子集選取問題。
一般情況下，0-1背包問題是NP難題。0-1背包
問題的解空間可用子集樹表示。解0-1背包問題的回溯法與裝載問題的回溯法十分類
似。在搜索解空間樹時，只要其左兒子結點是一個可行結點，搜索就進入其左子樹。當
右子樹有可能包含最優解時才進入右子樹搜索。否則將右子樹剪去。設r是當前剩餘
物品價值總和；cp是當前價值；bestp是當前最優價值。當cp+r≤bestp時，可剪去右
子樹。計算右子樹中解的上界的更好方法是將剩餘物品依其單位重量價值排序，然後
依次裝入物品，直至裝不下時，再裝入該物品的一部分而裝滿背包。由此得到的價值是
右子樹中解的上界。
2.解決辦法思路：
為了便於計算上界，可先將物品依其單位重量價值從大到小排序，此後只要順序考
察各物品即可。在實現時，由bound計算當前結點處的上界。在搜索解空間樹時，只要其左兒子節點是一個可行結點，搜索就進入左子樹，在右子樹中有可能包含最優解是才進入右子樹搜索。否則將右子樹剪去。
回溯法是一個既帶有系統性又帶有跳躍性的的搜索演算法。它在包含問題的所有解的解空間樹中，按照深度優先的策略，從根結點出發搜索解空間樹。演算法搜索至解空間樹的任一結點時，總是先判斷該結點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結點為根的子樹的系統搜索，逐層向其祖先結點回溯。否則，進入該子樹，繼續按深度優先的策略進行搜索。回溯法在用來求問題的所有解時，要回溯到根，且根結點的所有子樹都已被搜索遍才結束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可以結束。這種以深度優先的方式系統地搜索問題的解的演算法稱為回溯法，它適用於解一些組合數較大的問題。
2.演算法框架：
a.問題的解空間：應用回溯法解問題時，首先應明確定義問題的解空間。問題的解空間應到少包含問題的一個（最優）解。
b.回溯法的基本思想：確定了解空間的組織結構後，回溯法就從開始結點（根結點）出發，以深度優先的方式搜索整個解空間。這個開始結點就成為一個活結點，同時也成為當前的擴展結點。在當前的擴展結點處，搜索向縱深方向移至一個新結點。這個新結點就成為一個新的活結點，並成為當前擴展結點。如果在當前的擴展結點處不能再向縱深方向移動，則當前擴展結點就成為死結點。換句話說，這個結點不再是一個活結點。此時，應往回移動（回溯）至最近的一個活結點處，並使這個活結點成為當前的擴展結點。回溯法即以這種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結點時為止。
3.運用回溯法解題通常包含以下三個步驟：
a.針對所給問題，定義問題的解空間；
b.確定易於搜索的解空間結構；
c.以深度優先的方式搜索解空間，並且在搜索過程中用剪枝函數避免無效搜索；
#include<iostream>
using namespace std;
class Knap
{
friend int Knapsack(int p[],int w[],int c,int n );
public:
void print()
{
for(int m=1;m<=n;m++)
{
cout<<bestx[m]<<" ";
}
cout<<endl;
};
private:
int Bound(int i);
void Backtrack(int i);
int c;//背包容量
int n; //物品數
int *w;//物品重量數組
int *p;//物品價值數組
int cw;//當前重量
int cp;//當前價值
int bestp;//當前最優值
int *bestx;//當前最優解
int *x;//當前解
};
int Knap::Bound(int i)
{
//計算上界
int cleft=c-cw;//剩餘容量
int b=cp;
//以物品單位重量價值遞減序裝入物品
while(i<=n&&w[i]<=cleft)
{
cleft-=w[i];
b+=p[i];
i++;
}
//裝滿背包
if(i<=n)
b+=p[i]/w[i]*cleft;
return b;
}
void Knap::Backtrack(int i)
{
if(i>n)
{
if(bestp<cp)
{
for(int j=1;j<=n;j++)
bestx[j]=x[j];
bestp=cp;
}
return;
}
if(cw+w[i]<=c) //搜索左子樹
{
x[i]=1;
cw+=w[i];
cp+=p[i];
Backtrack(i+1);
cw-=w[i];
cp-=p[i];
}
if(Bound(i+1)>bestp)//搜索右子樹
{
x[i]=0;
Backtrack(i+1);
}
}
class Object
{
friend int Knapsack(int p[],int w[],int c,int n);
public:
int operator<=(Object a)const
{
return (d>=a.d);
}
private:
int ID;
float d;
};
int Knapsack(int p[],int w[],int c,int n)
{
//為Knap::Backtrack初始化
int W=0;
int P=0;
int i=1;
Object *Q=new Object[n];
for(i=1;i<=n;i++)
{
Q[i-1].ID=i;
Q[i-1].d=1.0*p[i]/w[i];
P+=p[i];
W+=w[i];
}
if(W<=c)
return P;//裝入所有物品
//依物品單位重量排序
float f;
for( i=0;i<n;i++)
for(int j=i;j<n;j++)
{
if(Q[i].d<Q[j].d)
{
f=Q[i].d;
Q[i].d=Q[j].d;
Q[j].d=f;
}
}
Knap K;
K.p = new int[n+1];
K.w = new int[n+1];
K.x = new int[n+1];
K.bestx = new int[n+1];
K.x[0]=0;
K.bestx[0]=0;
for( i=1;i<=n;i++)
{
K.p[i]=p[Q[i-1].ID];
K.w[i]=w[Q[i-1].ID];
}
K.cp=0;
K.cw=0;
K.c=c;
K.n=n;
K.bestp=0;
//回溯搜索
K.Backtrack(1);
K.print();
delete [] Q;
delete [] K.w;
delete [] K.p;
return K.bestp;
}
void main()
{
int *p;
int *w;
int c=0;
int n=0;
int i=0;
char k;
cout<<"0-1背包問題——回溯法 "<<endl;
cout<<" by zbqplayer "<<endl;
while(k)
{
cout<<"請輸入背包容量(c)："<<endl;
cin>>c;
cout<<"請輸入物品的個數(n)："<<endl;
cin>>n;
p=new int[n+1];
w=new int[n+1];
p[0]=0;
w[0]=0;
cout<<"請輸入物品的價值(p)："<<endl;
for(i=1;i<=n;i++)
cin>>p[i];
cout<<"請輸入物品的重量(w)："<<endl;
for(i=1;i<=n;i++)
cin>>w[i];
cout<<"最優解為(bestx)："<<endl;
cout<<"最優值為(bestp)："<<endl;
cout<<Knapsack(p,w,c,n)<<endl;
cout<<"[s] 重新開始"<<endl;
cout<<"[q] 退出"<<endl;
cin>>k;
}
四.分支限界法求解0-1背包問題
1.問題描述：已知有N個物品和一個可以容納M重量的背包，每種物品I的重量為WEIGHT，一個只能全放入或者不放入，求解如何放入物品，可以使背包里的物品的總效益最大。
2.設計思想與分析：對物品的選取與否構成一棵解樹，左子樹表示不裝入，右表示裝入，通過檢索問題的解樹得出最優解，並用結點上界殺死不符合要求的結點。
#include <iostream.h>
struct good
{
int weight;
int benefit;
int flag;//是否可以裝入標記
};
int number=0;//物品數量
int upbound=0;
int curp=0, curw=0;//當前效益值與重量
int maxweight=0;
good *bag=NULL;
void Init_good()
{
bag=new good [number];
for(int i=0; i<number; i++)
{
cout<<"請輸入第件"<<i+1<<"物品的重量:";
cin>>bag[i].weight;
cout<<"請輸入第件"<<i+1<<"物品的效益:";
cin>>bag[i].benefit;
bag[i].flag=0;//初始標志為不裝入背包
cout<<endl;
}
}
int getbound(int num, int *bound_u)//返回本結點的c限界和u限界
{
for(int w=curw, p=curp; num<number && (w+bag[num].weight)<=maxweight; num++)
{
w=w+bag[num].weight;
p=w+bag[num].benefit;
}
*bound_u=p+bag[num].benefit;
return ( p+bag[num].benefit*((maxweight-w)/bag[num].weight) );
}
void LCbag()
{
int bound_u=0, bound_c=0;//當前結點的c限界和u限界
for(int i=0; i<number; i++)//逐層遍歷解樹決定是否裝入各個物品
{
if( ( bound_c=getbound(i+1, &bound_u) )>upbound )//遍歷左子樹
upbound=bound_u;//更改已有u限界,不更改標志
if( getbound(i, &bound_u)>bound_c )//遍歷右子樹
//若裝入，判斷右子樹的c限界是否大於左子樹根的c限界，是則裝入
{
upbound=bound_u;//更改已有u限界
curp=curp+bag[i].benefit;
curw=curw+bag[i].weight;//從已有重量和效益加上新物品
bag[i].flag=1;//標記為裝入
}
}
}
void Display()
{
cout<<"可以放入背包的物品的編號為：";
for(int i=0; i<number; i++)
if(bag[i].flag>0)
cout<<i+1<<" ";
cout<<endl;
delete []bag;
}
Ⅲ 動態規劃的0-1背包問題，請高手解釋下代碼
這是清華演算法設計C++描述上的代碼吧？呵呵 我正巧讀過。
簡單解釋一下吧 在解釋之前你要知道動態規劃是一個自底向上的過程
這個演算法用到了一個二維數組m[][] 來存儲各個坐標的價值信息 所以橫坐標表示背包號碼 縱坐標表示背包容量從1到c
注意該演算法只能限制c是整數且每個背包的重量也是整數.
然後int jMax=min(w[n]-1,c);找出w[n]-1和 c之間的小者。
for(int j=0;j<=jMax;j++) m[n][j]=0;表示第n個物品不選 那麼所以價值為0
for(int j=w[n];j<=c;j++) m[n][j]=v[n];表示第n個物品選擇 所以價值為v[n]
for(int i=n-1;i>1;i--){
jMax=min(w[i]-1,c);
for(int j=0;j<=jMax;j++) m[i][j]=m[i+1][j];
for(int j=w[i];j<=c;j++) m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
}
表示自n-1到2逐層計算各m[i][j]的值 每一個m[i][j]的值都是根據上一層也就是m[i][j+1] 得到的 最後處理個第一層的邊界條件 m[1][c]就是所得答案了
Ⅳ 程序員都應該精通的六種演算法，你會了嗎
對於一名優秀的程序員來說，面對一個項目的需求的時候，一定會在腦海里浮現出最適合解決這個問題的方法是什麼，選對了演算法，就會起到事半功倍的效果，反之，則可能會使程序運行效率低下，還容易出bug。因此，熟悉掌握常用的演算法，是對於一個優秀程序員最基本的要求。
那麼，常用的演算法都有哪些呢？一般來講，在我們日常工作中涉及到的演算法，通常分為以下幾個類型：分治、貪心、迭代、枚舉、回溯、動態規劃。下面我們來一一介紹這幾種演算法。
一、分治演算法
分治演算法，顧名思義，是將一個難以直接解決的大問題，分割成一些規模較小的相同問題，以便各個擊破，分而治之。
分治演算法一般分為三個部分：分解問題、解決問題、合並解。
分治演算法適用於那些問題的規模縮小到一定程度就可以解決、並且各子問題之間相互獨立，求出來的解可以合並為該問題的解的情況。
典型例子比如求解一個無序數組中的最大值，即可以採用分治演算法，示例如下：
def pidAndConquer(arr,leftIndex,rightIndex):
if(rightIndex==leftIndex+1 || rightIndex==leftIndex){
return Math.max(arr[leftIndex],arr[rightIndex]);
}
int mid=(leftIndex+rightIndex)/2;
int leftMax=pidAndConquer(arr,leftIndex,mid);
int rightMax=pidAndConquer(arr,mid,rightIndex);
return Math.max(leftMax,rightMax);
二、貪心演算法
貪心演算法是指在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的局部最優解。
貪心演算法的基本思路是把問題分成若干個子問題，然後對每個子問題求解，得到子問題的局部最優解，最後再把子問題的最優解合並成原問題的一個解。這里要注意一點就是貪心演算法得到的不一定是全局最優解。這一缺陷導致了貪心演算法的適用范圍較少，更大的用途在於平衡演算法效率和最終結果應用，類似於：反正就走這么多步，肯定給你一個值，至於是不是最優的，那我就管不了了。就好像去菜市場買幾樣菜，可以經過反復比價之後再買，或者是看到有賣的不管三七二十一先買了，總之最終結果是菜能買回來，但搞不好多花了幾塊錢。
典型例子比如部分背包問題：有n個物體，第i個物體的重量為Wi，價值為Vi，在總重量不超過C的情況下讓總價值盡量高。每一個物體可以只取走一部分，價值和重量按比例計算。
貪心策略就是，每次都先拿性價比高的，判斷不超過C。
三、迭代演算法
迭代法也稱輾轉法，是一種不斷用變數的舊值遞推新值的過程。迭代演算法是用計算機解決問題的一種基本方法，它利用計算機運算速度快、適合做重復性操作的特點，讓計算機對一組指令(或一定步驟)進行重復執行，在每次執行這組指令(或這些步驟)時，都從變數的原值推出它的一個新值。最終得到問題的結果。
迭代演算法適用於那些每步輸入參數變數一定，前值可以作為下一步輸入參數的問題。
典型例子比如說，用迭代演算法計算斐波那契數列。
四、枚舉演算法
枚舉演算法是我們在日常中使用到的最多的一個演算法，它的核心思想就是:枚舉所有的可能。枚舉法的本質就是從所有候選答案中去搜索正確地解。
枚舉演算法適用於候選答案數量一定的情況。
典型例子包括雞錢問題，有公雞5，母雞3，三小雞1，求m錢n雞的所有可能解。可以採用一個三重循環將所有情況枚舉出來。代碼如下：
五、回溯演算法
回溯演算法是一個類似枚舉的搜索嘗試過程，主要是在搜索嘗試過程中尋找問題的解，當發現已不滿足求解條件時，就「回溯」返回，嘗試別的路徑。
許多復雜的，規模較大的問題都可以使用回溯法，有「通用解題方法」的美稱。
典型例子是8皇後演算法。在8 8格的國際象棋上擺放八個皇後，使其不能互相攻擊，即任意兩個皇後都不能處於同一行、同一列或同一斜線上，問一共有多少種擺法。
回溯法是求解皇後問題最經典的方法。演算法的思想在於如果一個皇後選定了位置，那麼下一個皇後的位置便被限制住了，下一個皇後需要一直找直到找到安全位置，如果沒有找到，那麼便要回溯到上一個皇後，那麼上一個皇後的位置就要改變，這樣一直遞歸直到所有的情況都被舉出。
六、動態規劃演算法
動態規劃過程是：每次決策依賴於當前狀態，又隨即引起狀態的轉移。一個決策序列就是在變化的狀態中產生出來的，所以，這種多階段最優化決策解決問題的過程就稱為動態規劃。
動態規劃演算法適用於當某階段狀態給定以後，在這階段以後的過程的發展不受這段以前各段狀態的影響，即無後效性的問題。
典型例子比如說背包問題，給定背包容量及物品重量和價值，要求背包裝的物品價值最大。
Ⅳ Python之動態規劃演算法
動態規劃演算法中是將復雜問題遞歸分解為子問題，通過解決這些子問題來解決復雜問題。與遞歸演算法相比，動態編程減少了堆棧的使用，避免了重復的計算，效率得到顯著提升。
先來看一個簡單的例子，斐波那契數列.
斐波那契數列的定義如下。
斐波那契數列可以很容易地用遞歸演算法實現：
上述代碼，隨著n的增加，計算量呈指數級增長，演算法的時間復雜度是 。
採用動態規劃演算法，通過自下而上的計算數列的值，可以使演算法復雜度減小到 ，代碼如下。
下面我們再看一個復雜一些的例子。
這是小學奧數常見的硬幣問題： 已知有1分，2分，5分三種硬幣數量不限，用這些硬幣湊成為n分錢，那麼一共有多少種組合方法。
我們將硬幣的種類用列表 coins 定義；
將問題定義為一個二維數組 dp，dp[amt][j] 是使用 coins 中前 j+1 種硬幣( coins[0:j+1] )湊成總價amt的組合數。
例如： coins = [1,2,5]
dp[5][1] 就是使用前兩種硬幣 [1,2] 湊成總和為5的組合數。
對於所有的 dp[0][j] 來說，湊成總價為0的情況只有一種，就是所有的硬幣數量都為0。所以對於在有效范圍內任意的j，都有 dp[0][j] 為1。
對於 dp[amt][j] 的計算，也就是使用 coins[0:j+1] 硬幣總價amt的組合數，包含兩種情況計算：
1.當使用第j個硬幣時，有 dp[amt-coins[j]][j] 種情況，即amt減去第j個硬幣幣值，使用前j+1種硬幣的組合數；
2.當不使用第j個硬幣時，有 dp[amt][j-1] 種情況，即使用前j種硬幣湊成amt的組合數；
所以： dp[amt][j] = dp[amt - coins[j]][j]+dp[amt][j-1]
我們最終得到的結果是：dp[amount][-1]
上述分析省略了一些邊界情況。
有了上述的分析，代碼實現就比較簡單了。
動態規劃演算法代碼簡潔，執行效率高。但是與遞歸演算法相比，需要仔細考慮如何分解問題，動態規劃代碼與遞歸調用相比，較難理解。
我把遞歸演算法實現的代碼也附在下面。有興趣的朋友可以比較一下兩種演算法的時間復雜度有多大差別。
上述代碼在Python 3.7運行通過。
Ⅵ 用C語言動態規劃演算法實現：某一印刷廠有六項加工任務，對印刷車間和裝訂車間所需時間見下表
#include<stdio.h>
int job[6][2]={
{3,8},
{12,10},
{5,9},
{2,6},
{9.3},
{11,1}
};
int x[6],bestx[6],f1=0,bestf,f2[7]={0};
void try(int i);
void swap(int a,int b);
int main(void)
{
int i,j;
bestf=32767;
for(i=0;i<6;i++)
x[i]=i;
try(0);
for(i=0;i<6;i++)
printf("%d ",bestx[i]);
printf("\nbestf=%d\n",bestf);
return 0;
}
void try(int i)
{
int j;
if(i==6)
{
for(j=0;j<6;j++)
bestx[j]=x[j];
bestf=f2[i];
}
else
{
for(j=i;j<6;j++)
{
f1=f1+job[x[j]][0];
if(f2[i]>f1)
f2[i+1]=f2[i]+job[x[j]][1];
else
f2[i+1]=f1+job[x[j]][1];
if(f2[i+1]<bestf)
{
swap(i,j);
try(i+1);
swap(i,j);
}
f1=f1-job[x[j]][0];
}
}
}
void swap(int i,int j)
{
int temp;
temp=x[i];
x[i]=x[j];
x[j]=temp;
}