Bajaruvchi: Istamov m tekshiruvchi: Axmedov f samarqand-2022 4-mavzu. “Dag‘al kuch” usuli. “Xasis” algoritmlar

Mavzu: Bog’langan graflarda marshrutlar, ularni narxi (masofasi) bo’yicha baholash.
Kerakli jihozlar: Kompyuter, proyektor, doska, C++ dasturlash tili
1-masala. Grafik uchlari ro'yxatini yaratish dasturini tuzing

1	3	13
1	4	14
2	1	12
3	1	13
5	1	15

Uning 3 ta yo'naltirilgan va 1 ta yo'naltirilmagan qirralari mavjud. Qiymatlarni formulaga almashtirib, biz qirralarning ro'yxatining balandligini olamiz: 3+1*2=5.
#include
using namespace std;
const int Vmax=100,
Emax=Vmax*(Vmax-1)/2; // agar grafik to'liq bo'lsa
int terminal[Emax], weight[Emax], point[Emax];
int head[Vmax], last[Vmax];
int n, m, v, u, w, k=0, i;
char r;
void Add(int v, int u, int w) // graf qirrasini qo'shish
{
k=k+1;
terminal[k]=u; weight[k]=w;
// agar v cho'qqisi yangi bo'lsa, unga tutash birinchi cho'qqi k raqamiga ega bo'ladi
if (head[v]==0) head[v]=k;
// agar v uchi allaqachon ko'rib chiqilgan bo'lsa,
// u holda unga qo'shni keyingi cho'qqi k raqamiga ega
if (last[v]!=0) point[last[v]]=k;
last[v]=k; }
int main() {
setlocale(LC_ALL,"Rus");
cout<<"Cho’qqilari soni >> "; cin>>n;
cout<<"qirralari soni >> "; cin>>m;
cout<<" Qirralarni va ularning og'irliklarini kiriting (v, u, w):\n";
for (i=0; i{
cin>>v>>u>>w;
cout<<" Qovurg'a orienti.? (y/n) >> "; cin>>r;
if (r=='y') Add(v, u, w);
else
{
Add(v, u, w);
Add(u, v, w);
}
cout<<"..."<}
m=m*2;
cout<<"graf qirralari ro’yxati:\n";
for (i=0; i{
k=head[i];
while (k>0)
{
cout<<"("<"<k=point[k];
}
}
return(0);
}
ko'rsatilgan grafikning dasturiy ta'minoti.

Mavzu: Xasis algoritmlar. Eng qisqa marshrutni aniqlash algoritmi. Uni variantlar soni bo’yicha hajmini baholash.
Kerakli jihozlar: Kompyuter, proyektor, doska, C++ dasturlash tili
1-masala. Sumka(рюкзак) masalasi

• 
  Aytaylik, Siz ochko’z o'g'risiz. Siz sumkangiz bilan do'kondasiz va u yerdagi narsalarni o'g'irlashingiz mumkin. Ammo siz faqat sumkangizga mos keladigan og’irlikdagi narsalarni olishingiz mumkin. Sumka 35 funtni ko’tarishi mumkin.
  
• 
  Siz sumka ichiga yig'ilishi mumkin bo'lgan maksimal qiymatga ega tovarlar to'plamini olishingiz kerak.
  

Siz sumka ichiga yig'ilishi mumkin bo'lgan maksimal qiymatga ega tovarlar to'plamini olishingiz kerak. Siz qanday algoritmdan foydalanasiz?
Bunda , Xasislik algoritm juda oddiy ko'rinadi:

• 
  Sumkaga to'g'ri keladigan eng qimmat narsani tanlang.
  
• 
  Sizning sumkangizga mos keladigan keyingi eng qimmat narsani tanlang ... va hokazo.
  

Ayrim vaqtlarda bu algoritm ishlamay qolishi mumkin.

Sumka umumiy og'irligi 35 funtdan oshmaydigan tovarlarga mos keladi. Eng qimmat mahsulot - magnitafon, siz uni tanlaysiz. Endi boshqa joy qolmadi.

Xasislik algoritmi bo’yicha yechim

Optimal yechim
Dastur kodi
#include
#include
using namespace std;
struct tovar
{
string nom;
int massa;
int narx;
};
int main()
{ //ma’lumotlarni kiritish;
vector mahsulot;
tovar k;
for(int i=0; i<3; i++)
{
cout< cin>>k.nom;
cin>>k.massa;
cin>>k.narx;
mahsulot.push_back(k);
}
//narx bo’yicha kamayish tartibida saralash
for(int i=0; i<2; i++)
for(int j=i+1; j<3; j++)
if(mahsulot[i].narx{
tovar temp=mahsulot[i];
mahsulot[i]=mahsulot[j];
mahsulot[j]=temp;
}
//eng qimmat narx bo’yicha sumkaga solish;
vector sumka;
int mSumka = 0;
int nSumka = 0;
for (int i=0;i<3;i++)
{
if(mSumka + mahsulot[i].massa <= 35)
{
mSumka+=mahsulot[i].massa;
nSumka+=mahsulot[i].narx;
sumka.push_back(mahsulot[i]);
}
}
//natijani ko'rish
cout<<"sumkada joylashtirilgan: "<<<" kg. umumiy narxi "<cout<<"-----------------------------------------------------"<cout<<"sumkada joylashritilgan mahsulotlar: "<for (int i=0;i{
cout<}
}