أعلانات الحراج بيت خشبي للسكن مساحة 100 م - كمبريشن للبيع - زبون كامل للأطفال - PSR-s 970 keyboard - للبيع gypsum board - TV cupboard - Casio Keyboard - String art boards - Yamaha PSR-E 203 portable electronic keyboard ( 61 full size keys) - Household Furniture (Double Bed, Cupboard, Chest etc.) - شاص شبح 2016 - مطلوب جهاز psp 3000 بي اس بي - دايزك للبيع جديد - خشب مستعمل للبيع ( لوح ورقه ومرتك) - شقه للبيع في ميدان السكاكيني بين الظاهر من شارع رمسيس - مطلوب كابل 4 في 16 - Ricoh refurbished printers with copier sscanner and documen server - بيع ركشات بالتقسيط - عمل بدي - دورة صيانة الهواتف ( software and hardware ) - مطلوب جرو روت وايلر عمر ما يجوز 4 اشهر العنده ï»» يقصر وشرط ذكر ما اريد نثيه - ستوديو مفروش في حي الخضراء تونس - انفلترمحول كهربا من المني فاز للتريفاز يصلح للمكنات الصناعيه - عارضات ميز تواليت ستان رفوف زجاج - 3 pcs coffee tables - ركنه للبيع - الماكينه السحريه اليابانيه 5 استخدامات في جهاز واحد - Dog training collar for sale - سيارة توصيل بالجوف - تنظيف وتعقيم خزانات المياه والفسقيات والنافورات وأحواض السباحة - Honda civic 2005 - The confession - Looking for Part Time Cook - مستودعات للايجار بالسلي - دوج تشارجر 2008 - دايو نوبيرا 2000.البيع. - شقة في الجبيهه خلف الاميره بسمه نزول تولين - $%&!#$ needs a loving home - We provide best cleaning solution for your offices, School and Home @ - اكاديمية ومدارس المشاهير للعلم و المعرفة - AraBella Building, Deddeh, 155 and 180 m2 new apartments for sale - فيلا للبيع -سوبر لوكس-صف اول على البحر-بكمبوند فوكة باي-الساحل - معلم خبير في تدريس اللغة العربية والعلوم الاسلامية - Spring Mattress - شقه ديلوكس عمرها سنتين للبيع بسعر مغري - Rocking Lounge Chair For Sale - معمل حلويات شرقيه وغرببه للببع - قطاعة خضار 10في1 - Code 2396 (1) Sofa Set 3 + 2 . - ديسكوات فيا 5 -
موقع الو طبيب محمد الصيدي الإدريسي - مكتب محامى حسام التنيب - يحيا زكريا الوعب - احمد سعيد النصاب - مطعم اصداف للبحريات - زهره ام مكوه - مكتب جاسم العلي خدم - كبب بيتنا اللذيذه ب11 ونص - دكتور بيطري جرش - وسييّم - تاجير سيارات النمسا - مطعم سماسم فطاير9تنفيذأحكام - مطعم الغمغام - مكثف سيرفس - مهندس ابواهبم - د . منيره مغربي - دعم العملاء الاتصالات - محاسب الدليل - جراره الرياض - علي المحامي أخو خليل شركة أوغلو تركيا - فندق دمشق الدولي/دمشق - Salman - نايف الوثلان - بسام م الجديعي - مطعم فطاير القادسية - ANAS.KHOTANI - تسويقار الدولية - الدكتوره نجود العجروش / استشارية جلدية مركز ديرما - بقاله ق1 - مكتب الشغالات - عبدو قرعوش - المحاميه عبير غازي الحداد - مؤسسة الشلوان وائ - ابو عبدالله المعهد - اياد الحارس بنك الاردن الكويت - مخبز تميس الفحيحيل - دكتور أعشاب اردني - مزرعة الشايب ابو تركي - عدنان علي الشمري - سفر وسياحه - عبدالله الشطي - شيميل المهبوله ريم - اللجنة الخاصة - موزع شركه ببسي مطعم - علي العمود ي 3 - ام مكوه - جوال المدرسة - الرواد العالميه 7 12 - عادل خضر البعثه - ابو حاتم القثامي -
الجديد شركة القُصير السعودية لتأجير وبيع الخيـام الأوروبية ومولدات الكهرباء - الصلاة الصلاة - كيف ازرع النعناع في المنزل ؟ - فوائد التمر والحليب - كيف توفر العديد من المال على نفسك ؟ - كيف تبداء بمشروع صغير وناجح ؟ - كيف تصبح غنياً ؟ - كيف توفر المال ؟ -
آخر المشاهدات هاتف وعنوان برجر كنج ميدل ايست ( الادارة العامة ) - الملز, مدينة الرياض - الجهاز الدوري المفتوح الجهاز الدوري المفتوح والجهاز الدوري المغلق - كلية التقنيات الصحية والطبية في بغداد نبذة عن الكلية - ثنائي الذرة غازات منفردة الذرات - اسباب مرض تشنج العمود الفقري - قائمة رؤساء تشيلي - متطلبات الحصول على تأشيرة العمرة فى سفارة السعودية بالاردن - حاصرات مستقبلات بيتا الأعراض الجانبية - هاتف وعنوان مكتب محمد الحماد للإستقدام - النسيم, مدينة الرياض - وصفة هائلة من الطب البديل لعلاج الروماتيزم أمراض العظام والمفاصل بالاعشاب - عيد اليحيى السيرة الذاتية - [بحث جاهز للطباعة] طريقة و طرق و كيفية كتابة تقرير و تقارير عن زيارة و طبي و مدرسي و صحفي فني اداري - - حي الندوه (الرياض) أهم الشوارع الرئيسية - طريقة تحضير الدشيشة بالذ طعم خطوة بخطوة - هاتف وعنوان مستوصف السلامة الأهلي - الباحه - هاتف وعنوان المستشفى الأهلي - خميس مشيط, عسير - طريقة عمل العجينة لجميع المعجنات من حلقات برنامج منال العالم - سرطان الثدي الالتهابي الاعراض - [بحث جاهز للطباعة] خاتمة بحث ديني علمي عربي قصيره - - الأمير عفاس بن محيا - الثمامية الموقع الجغرافي - ابن المنير السكندري آثاره - تضمين (إلكترونيات) التضمين التماثلي - طريقة عمل وصفة الكيك الاسفنجى على طريقة منال العالم - الدولة المرينية تاريخ - [بحث جاهز للطباعة] بحث عن حرب 6 اكتوبر 1973 بالصور pdf doc - - وصفة لعلاج التهاب المثانة ومشاكل المجاري البولية بالاعشاب الطبيعية - [بحث جاهز للطباعة] مشروع تخرج نظم معلومات , مشروع تخرج شبكات - - منهج إداري 1. المنهج الكلاسيكي Classical Appoarch - الدالة المحدودة - كربونات الكالسيوم الخواص - بلدية الرغاية الموقع الجغرافي - عمار بن ياسر نسبه - العلاج القرآني للسحر والمس الشيطاني (كتاب) الجزء الأول - مسدس صوت تحويل المسدس الصوت الي مسدس حي - بثينة بنت تيمور النشأة - لوحات تسجيل المركبات في تونس أصناف سلاسل التسجيل في تونس - طريقة تحضير القراقيش المصريه من الشيف منال العالم - [بحث جاهز للطباعة] بحث علمي جاهز عن الفيزياء - - وصفة هائلة من الطب البديل لعلاج النحافه و فقر الدم وضعف الجسم بالاعشاب - طريقة عمل سندويش تويستر بيتي الذ من كنتاكي لا تفوتك - سداسي أضلاع السداسي المنتظم - محي الدين بن عربي نشأته - هاتف وعنوان مشغل برزان - حائل - جزيرة الكنز ملخص الرواية - علاج الجلطة الدماغية و الشلل النصفي - هاتف وعنوان مطعم الطيب - الرويس, جدة - هواتف مستشفى الصحة النفسية و معلومات عنها بعسير بالسعودية - ضواحي أوغندا ضواحي أوغندا - معاهدة تافنة بنود المعاهدة - أسباب التوقف المفاجئ لوظائف الكليه - فولكس فاجن بولو تاريخها - زنبق البحر صفاته - طريقة تحضير فاهيتا الدجاج من الشيف منال العالم - عضلة شبه منحرفة المنشأ والمرتكز - ألم الرباط المستدير الأعراض - طريقة عمل وصفة الأرز بالكاري من اكلات منال العالم - [طبخات مميزة] طريقة عمل المهياوة بالصور،المهياوة بالصور،خطوات تحضيرالمهياوة بالصور - طبخ منزلي - علي بن حسين بن مسلم سيرته - مديح نبوي خصائص المديح النبوي - خلايا الأنبوب الغربالي - ملف شامل عن البارانويا - انقسام منصف (اختزالي) مراحل الانقسام المنصف - مناخ الجزائر خصائص المناخ في الجزائر - وجهات مصر للطيران مصر - هاتف وعنوان شركة الردادي للمطاعم البحرية - الحره الشرقيه, المدينة المنورة - يوجين نايدا حياته - ميزانية و تكاليف ودراسة جدوى مشروع ثلاجات التخزين - خوزيه كابابلانكا - معلومات هامة عن سلالة دجاج الجميزة - بقرة سويسرية بنية - تداخل الموجات التداخل البناء والتداخل الهدام - ابن جحاف تاريخه - على مر الزمان (مسلسل) قصة المسلسل - نظرية هوفستد للأبعاد الثقافية تاريخ ومنهجية البحث - نقطة تحول (مسلسل) قصة المسلسل - نظرية التفاعل الرمزي - فوائد مخلفات مجازر الدواجن في تغذية الدجاج - حصان (جنس) الخصائص الأحيائية - الإسلام حسب البلد الدول - قائمة أمراض نقص المناعة الأولية الفئة الأولى - طريقة تحضير المغربية اللبنانية من الشيف منال العالم - مزايا وعيوب شركات التوصية البسيطة وهل تصلح للمشروعات الصغيرة - سور القران لكل شهر من شهور الحمل - أكسيد البوتاسيوم الإنتاج - غيدا مجذوب حياتها - اسباب وعلاج ورم كابوسي اللحمي - بوشفاعة دواوير الجماعة - عظم القص أجزاء عظم القص - سلسلة بالمر مقدمة - وصفة هائلة من الطب البديل لعلاج القولون بالاعشاب - غائب في الربيع - هاتف وعنوان محلات السويلم للأجهزة الكهربائية - الديره, مدينة الرياض - سلسلة باون التفاعلية أساس النظرية - هاتف وعنوان مطعم المدينة - حوطة سدير, محافظات الرياض - هواتف مستشفى المجاردة و معلومات عنها بعسير بالسعودية - هاتف وعنوان مطعم ملك الفطائر - ابها, مدينة ابها - وصفة هائلة من الطب البديل لعلاج امراض القدم والارجل بالاعشاب - كيف يتم تشخيص داء هورتون - مقام بياتي اغاني على مقام البياتي - طريقة عمل ومقادير الرز المفلفل من مطبخ منال العالم - ارقام تلفونات مخافر الكويت والمراكز الامنية - ببر جاوي - ميثوكسي فلوران الاستخدام الطبي - طريقة عمل مشوي الجدر بطعم لذيذ لا تفوتكم - اعمال اخشاب الطوبار اعمال اخشاب الطوبار - خصائص الوصف انواع الوصف - قابلية القسمة ملاحظات - هاتف وعنوان مؤسسة عبد المحسن السويلم للأجهزة الكهربائية - الرويس, جدة - الخضراء (بني شهر) - مؤسسة القاضي لتركيب افضل اشكال الهناجر والسواتر والمظلات - عنوان وهواتف سفارة مالي فى السعودية ومعلوات عنها - منطق ثلاثي تعريفات - أشكال سطح الأرض أشكال اليابسة - رامانا العظيم - طريقة تحضير ستروغونوف باللحمة من الشيف منال العالم - البرتقالة المرة (فيلم) القصة - هاتف ومعلومات عن منتجع فانتزي لاند بالرياض - هاتف وعنوان مستوصف حامد التخصصي - محايل, عسير - غابرييلا سبانيك بداياتها و مراحل نجاحها - الجوسق الخاقاني - الأسطورة والخرافة والعلاقة بينهما مقدمة عن الأساطير - وصفة تساعد على التئام الجروح: بسرعة بخلطات الاعشاب - وصفات تعمل بالمنزل - إي سونغ من (1986) حياته - نظام النافذة إكس مبادئ تصميم س - توصيل الإشارة جزيئات التأشير - هاتف وعنوان مستوصف آل مترك - المزاحميه, محافظات الرياض - طريقة تحضير حلى الرخام من كتاب النخبة بطريقة سهلة - باع قياسات الباع - نايل دي ماركو خلفية - وصفة هائلة من الطب البديل لعلاج سلس البول والغائط بالاعشاب - سواقط الفاتحة - هاتف وعنوان مطعم العروبة - الخبر - هاتف وعنوان مطبخ العزائم للمندي - ينبع - دراسة جدوى لمشروع تسمين العجول البقري - هواتف مستشفى البشائر و معلومات عنها بعسير بالسعودية - جول ميشليه - علي الطالقاني (الولادة) - كيف تكون رجل مبيعات ناجح للدكتور ابراهيم الفقي - منصور الثاني بن ناصر بن عبد العزيز آل سعود نشأته ودراسته - هيدروكسيد البوتاسيوم التحضير - قانون السعر الواحد ما هو الفرق بين تعادل القوى الشرائية وقانون السعر الواحد؟ - طلخا أهم المشاهير - شرح تركيب وكيفية عمل الغسالة الاتوماتيك من قسم الاصلاح والصيانة - وصفة لعلاج التهاب المفاصل و آلام العضلات بخلطات الاعشاب - وصفات تعمل بالمنزل - تعريف النص الوصفي - مملكة المسبعات الموقع - منشار أنواع المناشير - قائمة منتجات مصر للبترول زيوت مصر للمحركات - علي بن مجثل المغيدي مولده ونشأته - السيد أبو العربي وصل (فيلم) قصة الفيلم - الإعلام في ليبيا تاريخ التلفزيون في ليبيا - هاتف وعنوان المستشفى التخصصي بأبها - ابها, مدينة ابها - يصبوغ - تسرع القلب فوق البطيني الأسباب - الحمى المالطيه Brucillosis مرض معدى يتميز بارتفاع في درجة الحرارة - مستشعر الحساسات الضوئية - طريقة تحضير عجينه بيتزا هت،بيتزا هت بطريقة سهلة - نترات الباريوم الخواص - نغم ساحر نغمٌ ساحرٌ - السابقون الأولون أسماء السابقين الأولين - طريقة عمل وصفة سلطه الكاتشب والشطه الشهية - طريقة تحضير خلية نحل الجالكسي بالصور بطريقة سهلة - وصفة هائلة من الطب البديل لعلاج التهاب الحنجره التهاب الحلق بالاعشاب - طريقة تحضير معجنات عمة ترباس من المطبخ السوداني بطريقة سهلة - هاتف وعنوان مطاعم حمص ريفي للمقبلات - سلطانه, المدينة المنورة - كيف تبداء بمشروع صغير وناجح ؟ - نظرية التوطن الصناعي مقدمة - تدلي الحبل السري تصنيف - ما وراء الطبيعة (أرسطو) اسم الكتاب - خوان الغول (مسلسل) القصة - هاتف وعنوان مركز خالد للعلاج الطبيعي - الجامعه, الاحساء - برينا ايفيجن حياتها - حجم قضيب الإنسان الحجم - هاتف وعنوان مكتب استقدام الباشا - الطائف وج, الطائف - قانون ليبيا موسوعة التشريعات الليبية - وصفة هائلة من الطب البديل لعلاج مشاكل الدوره الشهرية و الحيض بالاعشاب - رواية (أدب) عناصر بناء الرواية - فرط ثنائي أكسيد الكربون في الدم الأسباب - هنري فايول إنجازات - هاتف وعنوان مستشفى السلام - مكه الخريق, مكة المكرمة - هاتف وعنوان مطعم المركاز - محايل, عسير - وصفة لعلاج الربو و حساسية الصدر بالاعشاب الطبيعية - هاتف وعنوان مستوصف السلام - عنيزه, القصيم - عبد الله بن غصاب السيرة الذاتية - هاتف وعنوان مشغل الأول النسائي - الجامعه, الاحساء - محرك كهربائي عديم المسفرات مقارنة بين محركات المسفرات ومحركات عديمة المسفرات - قائمة الكنائس في سوريا الكاتدرائيات في سوريا - عثمان بلوزداد - هواتف شركة فن المعمار السعودية للصيانة المحدودة ومعلومات عنها بالسعودية - دالة الإمكان - كيف توفر العديد من المال على نفسك ؟ - وصفة هائلة من الطب البديل لعلاج تساقط الشعر و قشرة الرأس Dandruff بالاعشاب - ورل أنواع الوَرَل - كفر المنشي أبو حمر السكان - راجل وست ستات (مسلسل) الشخصيات الرئيسية - طريقة عمل اكلة الكيما من مطبخ منال العالم - خروب وصف شجرة الخروب - هاتف وعنوان مطعم القصر - ينبع - تفاعل كانيزارو -
اليوم: الجمعة 19 اكتوبر 2018 , الساعة: 2:54 م / اسعار صرف العملات ليوم الجمعة 19/10/2018


اعلانات
محرك البحث


مسألة حقيبة الظهر

نشر قبل 2 سنة 332 مشاهدة


اعلانات
شاركنا رأيك بالموضوع

مشكلة نابساك

مشكلة الحقيبة (نابساك) أو (راكساك)؛ هي مشكلة تحدث في عملية التحسين التوافقي. حيث يتواجد عدد من المواد، لكلٍّ وزنها وقيمتها. المطلوب هو تحديد العدد المتضمن في المجموعة من كل مادة بحيث يكون إجمالي الوزن أقل من أو مساوٍ للحد المطلوب، وتبلغ القيمة الإجمالية أكبر قدر ممكن. تستمد المشكلة اسمها من العقبة التي يواجهها الشخص عند تقييده بحقيبة ذات حجم ثابت عليه ملؤها بالمواد ذات القيمة الأعلى.

غالياً ما تنشأ المشكلة عند القيام بتخصيص الموارد، حيث تتواجد قيود مالية. ويتم دراستها في مجالات معينة؛ مثل التوافقية، وعلوم الكمبيوتر، ونظرية التعقيد، والترميز، والرياضيات التطبيقية، والرياضات الخيالية اليومية.

وقد تمت دراسة مشكلة الحقيبة (نابساك) لأكثر من قرن، مع الأعمال المبكرة التي يرجع تاريخها إلى عام 1897 للميلاد. ويعود اسمها إلى الأعمال المبكرة لعالم الرياضيات توبياس دانتزغ (1884-1956). وتشير المشكلة إلى المشكلة الشائعة المتعلقة بحزم المواد الأكثر قيمة وفائدة دون التسبب بإثقال الأمتعة.


التطبيقات

أثبتت دراسة سجل الخوارزميات في جامعة ستوني بروك التي أجريت عام 1998 أنه من أصل 75 مشكلة حسابية، احتلت (النابساك) المرتبة الثامنة عشر كأكثر المشاكل شعبية والرابعة من حيث الأكثر حاجة بعد الkd-trees ومشكلة التعبئة بن.

تظهر مشكلة الحقيبة (النابساك) في عملية صناعة القرار على ارض الواقع في كافة المجالات، مثل ايجاد الطريقة الأقل تكلفة لقطع المواد الخام، واختيار الاستثمارات والقضايا، والتوريق المالي للأصول المدعومة، وتوليد المفاتيح لميركيل-هيلمان، وغيرها من نظم الترميز باستخدام النابساك.

من إحدى التطبيقات المبكرة التي استخدمت خوارزمية النابساك كانت في عملية بناء وتمرير الاختبارات. بحيث أن من يأخذ الاختبار له الحرية في اختيار الأسئلة التي يريد أن يجيب عليها. في أمثلة بسيطة كهذه يكون من السهل تزويد المتقدمين للاختبار بهذا الخيار. مثال إذا كان الاختبار يحتوي على 12 سؤالا، كل سؤال ب10 نقاط. للحصول على أعلى نتيجة يتوجب على من يأخذ الاختبار حل 10 أسئلة فقط للحصول على 100 نقطة، ولكن في الاختيارات التي لا تحتوي على توزيع متساوٍ للنقاط يصبح من الصعب التزويد بخيارات للحل. اقترح فيورمان ووايس نظاما يُعطى فيه الطالب اختبارا غير متجانس مع ما مجموعه 125 نقطة ممكنة. يطلب من الطلاب إجابة جميع الأسئلة باستخدام أفضل قدراتهم. فيما يتعلق بالمجموعات الفرعية المحتملة للمشاكل التي تصل قيمة نقاطها إلى 100، فإن خوارزمية الحقيبة (نابساك) ستحدد أي من المجموعات الفرعية ستقدم للطالب أعلى درجة ممكنة.




التعريف

المشكلة الأكثر شيوعا التي يتم حلها هي مشكلة نابساك 0-1، التي يتم فيها ترقيم عدد (xi) من النسخ من كل نوع ب 0أو 1. مع إعطاء مجموعة من المواد أرقاماً من 1إلى (n). كلٌ له وزنه (wi) وقيمته (vi)، بالإضافة إلى الحد الأقصى لسعة الوزن (W)،

maximize

subject to and .


نلاحظ أن (xi) تمثل عدد حالات وضع المادة (i) في الحقيبة. والمشكلة هي تحقيق أقصى قدر ممكن من مجموع قيم المواد الموجودة في الحقيبة، بحيث يكون مجموع الأوزان أقل من أو يساوي قدرة الحقيبة.

تزيل مشكلة الحقيبة المحدودة (BKP) القيد المتمثل بوجود قطعة واحدة من كل مادة، إلا أنها تحد العدد (xi) من النسخ لكل نوع من المواد بعدد صحيح ( )

maximize

subject to and



لا تضع مشكلة الحقيبة غير المحدودة حد أعلى لعدد النسخ من كل نوع من المواد. ويمكن صياغتها على النحو الوارد أعلاه، باستثناء أن القيد الوحيد على (xi)هو أنه عدد صحيح غير سالب.

Maximize

subject to and


هناك مثال على مشكلة الحقيبة غير المحدودة موضَّح من خلال الشكل المرفق في بداية هذه المقالة مع تسميته التوضيحية.



التعقيد الحسابي

تعتبر مشكلة الحقيبة (نابساك) مثيرة للاهتمام من وجهة نظر علم الحاسوب لأسباب عديدة

• إن قرار أخذ المادة أو عدمه يتم حسابه بصيغة متعدد الحدود؛ لذلك لا يوجد أي خوارزمية معروفة صحيحة وسريعة (بوقت متعدد الحدود) لكل الحالات.

• باعتبار أن مشكلة اتخاذ القرار تعتبر متعدد حدود كامل، فإن عملية تحسين حل المشكلة تعد غير محدودة بمتعدد الحدود، ووضوحها لا يقل صعوبة عن مشكلة اتخاذ القرار، ولا يوجد أي خوارزمية متعددة الحدود تستطيع تحديد ذلك عن طريق تقديم حل، حتى لو كان مثاليا (الذي قد يعني أنه لا يوجد حل باستخدام قيمة أعلى، وبذلك حل مشكلة اتخاذ القرار متعددة الحدود).

هناك خوارزمية شبه متعددة الحدود باستخدام البرمجة الديناميكية.


هناك رابط بين مشاكل اتخاذ القرار وإيجاد الحل الأمثل في أنه إن كان هناك وجود لخوارزمية متعددة الحدود تستطيع حل مشكلة اتخاذ القرار، فإنه من الممكن للشخص إيجاد القيمة القصوى لمشكلة الحل الأمثل بالوقت متعدد الحدود من خلال تطبيق هذه الخوارزمية بشكل متكرر بينما قيمة k تزداد. من ناحية أخرى، إذا قامت خوارزمية بإيجاد القيمة المثلى لإيجاد الحل الأمثل بوقت متعدد الحدود، فإنه من الممكن حل مشكلة اتخاذ القرار بوقت متعدد الحدود من خلال مقارنة قيمة الحل الناتج عن طريق هذه الخوارزمية مع قيمة k. وهكذا فإن كلتا النسختين من المشكلة تتشاركان نفس الصعوبة.

يعتبر تحديد الحالات الصعبة من مشكلة الحقيبة (نابساك)، أو تحديد خاصيات الحالات التي من الممكن أن تجعلها أكثر قابلية مما يقترحه أسوأ سلوك متعدد الحدود المكتمل، أحد مواضيع أدبيات البحث. الهدف من إيجاد هذه الحالات الصعبة يكمن في استخدامها في أنظمة التشفير باستخدام المفتاح العام، تماما مثل ترميز حقيبة ميركيل-هيلمان.













الحل

مشكلة نابساك 0-1

إن حل مشكلة نابساك 0-1 يكمن في الوقت شبه متعدد الحدود. لنفترض أن هي مجموعة أعداد صحيحة موجبة، حدد لتكون أعلى قيمة يمكن الحصول عليها مع مراعاة أن يكون الوزن أقل من أو يساوي باستخدام مواد قد يصل عددها إلى .

بإمكاننا تحديد بشكا متكرر على النحو التالي



• if (تساوي المادة الجديدة أكثر من حد الوزن الحالي)

• if .

من الممكن إيجاد الحل عن طريق حساب . للقيام بذلك بكفاءة يمكننا استخدام جدول لتخزين العمليات الحسابية السابقة.

فيما يلي توضح البرمجية المبدئية للبرنامج الديناميكي

1. // Input

2. // Values (stored in array v)

3. // Weights (stored in array w)

4. // Number of distinct it s (n)


5. // Knapsack capacity (W)

6.

7. for j from 0 to W do

8. m[0, j] 0

9.

10. for i from 1 to n do

11. for j from 0 to W do

12. if w[i-1] > j then
13. m[i, j] m[i-1, j]

14. else

15. m[i, j] max(m[i-1, j], m[i-1, j-w[i-1 + v[i-1])


فإذن سيطبق هذا الحل في وقت ومساحة . بالإضافة إلى ذلك، إذا لم نستخدم سوى مجموعة أحادية الأبعاد لتخزين القيم المثلى الحالية والمرور على هذه المجموعة i+1 مرات، وإعادة الكتابة من ألى كل مرة، فإننا سنحصل على ذات النتيجة لمساحة فقط.

شريط بوابات برمجة الحاسوب معلوماتية رياضيات


تصنيف أبحاث العمليات

تصنيف استمثال توافقي

تصنيف بحوث عمليات

تصنيف برمجة خطية

تصنيف برمجة ديناميكية

تصنيف تعمية

تصنيف خوارزم

تصنيف مسائل NP كاملة
 
التعليقات

لم يعلق احد حتى الآن .. كن اول من يعلق بالضغط هنا

اعلانات
تصنيفات الموقع
شاهد الجديد لهذه المواقع
بئر السبع ميسوكسيمايد تل هشومير المرجة الزرقاء أسامة بن زيد الغاف دراسة جدوى خطة عمل روبرك الطاقة الداخلية مذكرات دورية نحو الشرق ايو جيما العياضي برباس العياضي شركة مكافحة حشرات خوارزمية ديكسترا مرفأ بيروت الكايد طاش ما طاش شركة كايد البسقلون كورونا سد حراض الفن البيزنطي عبد السلام بنعبد العالي رائد عودة مستشفى طيبة التخصصي غزوة خيبر شركة فواز لعامة للدراسات والمستندات كلوفيس الأول لمع قطع الغيار جميل خطاب ويلان نظم المعلومات المحاسبية محمود بن محمود البان باقادر مؤسسة بن شيهون الصحة الحقن المجهري الصين معلمات معلومات اتجاه البطولي أرضروم تنافسية شكاوي محمد الحاج سالم تكرلي مبرهنة عدم الاكتمال علاج عرق النسا موقع سنهدريم التكامل العددي كهربا الحكومة الحكومة التونسية مسالك بولية معاهدة فاليتا مستشفي بدر مشاغل مراكز التجميل محمد حافظ الشريدة وديع سعادة مشغل جرافيزم شكا الربان حديقة التجارة نقليات الهباس بن دعجم بطباط حمود بوعلام حميدة معركة ثابسوس براتا البن الاخضر مشروع تخرج الزكاه ديدفورت تاريخ فواصل الكتب توسعة المسجد النبوي نادي الفتح telnet 1978 عصبام اللوزتين سبيكمان 213 الاقتصاد رمادي عادي فندق العليا تشويه سمعه اسماك الأسماك مؤسسة
أخبار السعودية اليوم الجمعة 19/10/2018 - أخبار قطر اليوم الجمعة 19/10/2018 - أخبار الإمارات اليوم الجمعة 19/10/2018 - أخبار الكويت اليوم الجمعة 19/10/2018 - أخبار السياحة اليوم الجمعة 19/10/2018 - أخبار البحرين اليوم الجمعة 19/10/2018 - أخبار المغرب اليوم الجمعة 19/10/2018 - أخبار الاردن اليوم الجمعة 19/10/2018 - أخبار فلسطين اليوم الجمعة 19/10/2018 - أخبار عمان اليوم الجمعة 19/10/2018 - أخبار لبنان اليوم الجمعة 19/10/2018 - أخبار السودان اليوم الجمعة 19/10/2018 - أخبار الكورة اليوم الجمعة 19/10/2018 - اعلانات الحراج اليوم الجمعة 19/10/2018 - اسعار السيارات بالكويت الجمعة 19/10/2018 - اسعار العقارات بالكويت الجمعة 19/10/2018