算法分析大作业

#include %using namespace std; #define INF 10000 /*

f[i][j][0]表示汽车从网格点(1,1)行驶至网格点(i,j)所需的最少费用 f[i][j][1]表示汽车行驶至网格点(i,j)还能行驶的网格边数

s[i][0]表示x轴方向 s[i][1]表示y轴方向 s[i][2]表示行驶费用

f[i][j][0] = min{f[ i+s[k][0] ][ [j+s[k][1] ][0] + s[k][2]} f[i][j][1] = f[ i+s[k][0] ][ [j+s[k][1] ][1] - 1;

f[1][1][0] = 0 f[1][1][1] = K

f[i][j][0] = f[i][j][0] + A , f[i][j][1] = K 如果(i, j)是油库 f[i][j][0] = f[i][j][0] + C + A, f[i][j][1] = K (i, j)不是油库，且f[i][j][1] = 0 */

int N; //方形网络规模

int A; //汽车在行驶过程中遇到油库应加满油并付加油费A

int C; //在需要时可在网格点处增设油库，并付增设油库费用C（不含加油费A）

int B; //当汽车行驶经过一条网格边时，如果其x坐标或y坐标减少，应付费用B

int K; //装满油后，还能行驶K条边

int f[50][50][2];

int s[4][3] = {{-1,0,0},{0,-1,0},{1,0,B},{0,1,B}};

int a[50][50]; //方形网络

int dyna() {

int i, j, k; for (i=1;i<=N;i++) {

for (j=1;j<=N;j++) {

f[i][j][0]=INF; f[i][j][1]=K; } }

f[1][1][0] = 0; f[1][1][1] = K;

int count = 1; int tx, ty; while(count) {

count = 0;

for(i=1; i<=N; i++) {

for(int j=1; j<=N; j++) {

if(i==1 && j==1) continue; int minStep = INF; int minDstep; int step, dstep;

for(k=0; k<4; k++) //可走的四个方向 {

tx = i + s[k][0]; ty = j + s[k][1];

if(tx<1 || ty<1 || tx>N || ty>N) //如果出界

continue;

step = f[tx][ty][0] + s[k][2]; dstep = f[tx][ty][1] - 1; if(a[i][j] == 1) //如果是油库 {

step += A; dstep = K; }

if(a[i][j]==0 && dstep == 0 && (i!=N||j!=N)) //如果不是油库,且油已经用完 {

step += A + C; dstep = K; }

if(step < minStep) //可以走 {

minStep = step; minDstep = dstep; }

}

if(f[i][j][0] > minStep) //如果有更优解 {

count++;

f[i][j][0] = minStep; f[i][j][1] = minDstep; } } } }

return f[N][N][0]; }

int main() {

ifstream fin(\ cout << \输入方格规模：\ fin >> N; cout << N;

cout << \输入装满油后能行驶的网格边数：\ fin >> K; cout << K; cout << \输入加油费：\ fin >> A; cout << A;

cout << \输入坐标减少时应付的费用：\ fin >> B; cout << B; s[2][2] = s[3][2] = B; cout << \输入增设油库费用：\ fin >> C; cout << C;

cout << \输入方形网络：\\n\ for(int i=1; i<=N; i++) {

for(int j=1; j<=N; j++) {

fin >> a[i][j];

cout << a[i][j] << \ }

cout << endl; }

cout << \最优行驶路线所需的费用为：\ fin.close(); return 0; }

2.5最终结果

3.总结

动态规划（Dynamic Programming， DP）思想启发于分治算法的思想，也是将复杂问题化解若干子问题，先求解小问题，再根据小问题的解得到原问题的解。但是DP与分治算法不同的是，DP分解的若干子问题，往往是互相不独立的，这时如果用分治算法求解，那么会对重叠子问题重复进行求解，从而使得浪费大量的时间。那么如果我们保存已经计算过的子问题的解，这样当再次计算该子问题时，可以直接使用，这样可以节约大量的时间。 设计动态规划的四个步骤： 1、刻画一个最优解的结构特征。 2、递归地定义最优解的值。

3、计算最优解的值，通常采用自底向上的方法。 4、利用计算出的信息构造一个最优解。