Mavzu: Xasis algoritmlar. Eng qisqa marshrutni aniqlash algoritmi. Uni variantlar soni bo’yicha hajmini baholash

Mavzu: Xasis algoritmlar. Eng qisqa marshrutni aniqlash algoritmi. Uni variantlar soni bo’yicha hajmini baholash

Mavzu: Xasis algoritmlar. Eng qisqa marshrutni aniqlash algoritmi. Uni variantlar soni bo’yicha hajmini baholash.

Algoritmlarni loyihalash fani

11.2 laboratoriya mashg’uloti

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.

• 
  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

• 
  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;
  
• 
  }