4 laboratoriya ishi mavzu: Dinamik dasturlash masalasini yechish Ishning maqsadi

Dastur kodi

#include

#include

#include

const int nm=5;

int a[nm][nm];

int n;

void makebase(int ik, int jk)

{

int i,j;

for (i=0;i=0) a[i][jk]=-1;

for (j=0;j=0) a[ik][j]=-1;

a[ik][jk]=-2;

if (a[jk][ik]>=0) a[jk][ik]=-1;

}

void main()

{

int i,j,c,i2,j2,i3,j3;

int cnt;

int minv, miniv, minjv, maxv;

int flag;

ifstream f("mx.txt");

f >> n;

for (i=0;i> a[i][j];

f.close();

for (i=0;i

for (c=0;c

{

// looking for one-in-row or one-in-col element

flag=0;

for (i=0;(i

{

cnt=0;

for (j=0;j=0)

{

i2=i;

j2=j;

cnt++;

}

if (cnt==1) flag=1;

}

for (j=0;(j

{

cnt=0;

for (i=0;i=0)

{

i2=i;

j2=j;

cnt++;

}

if (cnt==1) flag=1;

}

if (flag==1)

{

makebase(i2,j2);

continue;

}

// minus mins

for (i=0;i

{

minv=30000;

for (j=0;j

if ((a[i][j]>=0)&&(a[i][j]

for (j=0;j=0) a[i][j]-=minv;

}

for (j=0;j

{

minv=30000;

for (i=0;i

if ((a[i][j]>=0)&&(a[i][j]

for (i=0;i=0) a[i][j]-=minv;

}

// checking nulls and looking for base values

maxv=-1;

for (i=0;i

{

miniv=30000;

minjv=30000;

for (i2=0;i2=0)&&(i2!=i)&&(a[i2][j]

for (j2=0;j2=0)&&(j2!=j)&&(a[i][j2]

if (miniv+minjv>maxv)

{

maxv=miniv+minjv;

i3=i;

j3=j;

}

}

makebase(i3,j3);

}

// output

clrscr();

i2=0;

cout << i2+1;

for (c=0;c

{

for (j=0;j

{

cout << "->" << j+1;

i2=j;

break;

}

}

getch();

}

Dasturni ishga tushirishdan oldin, siz shaharlarning soni va harakatlanuvchi matritsani o'z ichiga olgan matn faylini yaratishingiz kerak, masalan:

Dasturni ishga tushirgandan so'ng, u tarmoqlar va chegaralar usulini amalga oshiradi va eng qisqa yo'lni ko'rsatadi

Har qanday tugmachani bosgandan so'ng, dastur o'z ishini tugatadi.

TOPSHIRIQ:

Topshiriq variantlari. Kommivoyajer masalasini yechishning algoritmi va dasturini tuzing. Quyidagi ma’lumotlar asosida dasturni bajaring va hisobot yozing. Variant raqami talabaning jurnaldagi tartib raqamiga mos bo’lishi kerak.

1) 6 9 2 4 6 2 6 2 6 3 3 3 5 7 3 6 3 2 2 5

2) 9 12 7 10 9 7 2 4 2 4 3 5 8 7 1 5 3 4 3 5