4-Laboratoriya ishi Tayyorladi: 106-19-guruh talabasi Raxmatullayev J. Qabul qildi: Abdukarimov A. Samarqand 2023 Mavzu : Chiziqli dasturlashda optimallashtirish masalasi modeli va algoritmini qurish

4-laboratoriya ishi
Masalaning berilishi: Jadvallar nazariyasi masalasi. Djonson algoritmidan foydalanib masalani operatsiyalarni optimal tartiblash.
Jadvallar nazariyasi, ma'lumotlarni o‘z ichiga olgan jadvallar va ular orasidagi munosabatlarni tavsiflashga asoslangan tez-tez qo‘llaniladigan usul hisoblanadi. Bu usulda dasturlar tuzilishini osonlashtirish, yahshiroq mantiqiy yechim topish va amalda ham ish faoliyatini kuzatish imkonini beradi.
Masalaning berilishi: bizga 10 xil tanga (misol uchun, 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000 so‘m) berilgan va biz bitta mahsulot sotib olishimiz kerak. Bizning maqsadimiz, mahsulot narxini berilgan tangalar kombinatsiyalari bilan to‘liq to‘lash imkonini topishdir.
Masalaning yechimi: Djonson algoritmi, jadvallar orasida birinchi qadamda yechimni topish uchun ishlatiladigan, eng kichik yolg‘onni topishda ishlatiladigan tez-tez ishlatiladigan bir algoritmdir. Ushbu algoritmni quyidagi tartibda amalga oshirish mumkin:
1.Tangalardan katta bo‘lmagan eng kichik tangani topish. Misol uchun, agar bizning mablag‘imiz 73 so‘m bo‘lsa, eng kichik tangamiz 50 so‘m bo‘ladi.
2.Eng kichik tangadan keyingi mablag‘atlarni yana qoldiq narxlari orqali topish.
3.Qoldiq mablag‘atni eng kichik tangadan katta bo‘lmagan eng kichik tangaga qo‘shing va yana qoldiq mablag‘atni toping.
4. 3-qadamni o‘tkazib yana qoldiq mablag‘atni eng kichik tangadan katta bo‘lmagan eng kichik tangaga qo‘shishni takrorlang, to‘ki mablag‘at qolmasligi yoki mablag‘at mablag‘imizni tashkil qilishni yakunlang.
Shunday qilib, Djonson algoritmi yordamida mahsulot sotib olish jarayonida tangalar kombinatsiyalarini to‘liq to‘lash imkonini topish mumkin.
Masalaning yechimining dastur kodi C++ tilida:
#include
#include
#include

using namespace std;

void optimal_tartiblash(vector tangalar, int narx) {
sort(tangalar.rbegin(), tangalar.rend()); // Tangalarni katta dan kichik ga saralash
int qolgan_mablag = narx;
int index = 0;
while (qolgan_mablag > 0 && index < tangalar.size()) {
if (tangalar[index] <= qolgan_mablag) { // Eng kichik tangani topish
cout << tangalar[index] << " ";
qolgan_mablag -= tangalar[index];
} else {
index++; // Katta bo'lgan tangalarga o'tish
}
}
}

int main() {

vector tangalar = {1, 2, 5, 10, 20, 50, 100, 200, 500, 1000}; // 10 ta tangalar
int narx = 73; // Mahsulot narxi
optimal_tartiblash(tangalar, narx); // Tartiblangan tangalar
return 0;
}

Masalaninh konsul oynadagi javobi