تحليل موجز لخوارزمية جافا الجشع

الفكرة الأساسية لخوارزمية الجشع

1. إنشاء نموذج رياضي لوصف المشكلة.

2. قسّم المشكلات التي تم حلها إلى عدة مشكلات فرعية.

3. حل كل مشكلات فرعية والحصول على الحل الأمثل المحلي للمشكلات الفرعية.

4. توليف الحل الأمثل المحلي للمشاكل الفرعية في حل للحل الأصلي للمشكلة.

عملية تنفيذ هذه الخوارزمية:

بدءا من حل أولي معين للمشكلة ؛

في حين يمكن أن تتحرك إلى الأمام إلى هدف عام معين

ابحث عن عنصر حل في الحل الممكن ؛

يتكون الحل الممكن للمشكلة من جميع عناصر الحل.

الطبيعة الانتقائية الجشع

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

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

نسخة الكود كما يلي:
الجشع (C) // C هي مجموعة إدخال المشكلة ، أي مجموعة المرشح
{
S = {} ؛
في حين أن (ليس الحل (S)) // Set S لا يشكل حلاً للمشكلة
{
X = SELECT (C) ؛
إذا كان ذلك ممكنًا (s ، x) // ادكى على ما إذا كان الحل بعد إضافة x إلى مجموعة s أمر ممكن
s = s+{x} ؛
c = c- {x} ؛
}
العودة s ؛

وصف المشكلة:

حاليًا ، هناك عملات مع قيم الوجه 2 Jiao 5 Cents ، 1 Jiao 5 Cents ، 5 Cents و 1 Cents.

تحليل المشكلة:

وفقًا للمعنى السليم ، عندما نذهب إلى المتجر لشراء الأشياء وإيجاد المال ، يعطينا الرئيس دائمًا أقصى قدر من الطائفة. إذا طلب منك الرئيس الدرجات أو بضع سنتات ، فلن تفعل ذلك بالتأكيد. في الواقع ، هذه مشكلة نموذجية للاختيار الجشع.

تصميم الخوارزمية وتنفيذ المشكلة :

اسمحوا لي أن أعطيك مثالاً أولاً. يبحث عن ذلك مثل هذا؟ "هل تفعل ذلك ، ثم يمكن للمدرب أن يعطيني فقط أنني حصلت على 3 نقاط وحصلت على 24 نقطة أقل ، لذلك كان عليّ أن أعطيني 2 نقطة و 4 نقاط 1.

نسخة الكود كما يلي:
// الحساب لإيجاد التغيير
// الإدخال: Array M ، قم بتخزين عدد قيم الوجه المرتبة من كبيرة إلى صغيرة في التسلسل.
// الإخراج: صفيف NUM ، قارن عدد العملات المعدنية ذات قيم الفئة المختلفة في Array M ، وابحث عن خطة المال
int static int [] Zhaoqian (int m [] ، int n)
{
int k = m.length ؛
int [] num = new int [k] ؛
لـ (int i = 0 ؛ i <k ؛ i ++)
{
num <i> = n/m <i> ؛
n = n ٪ m <i> ؛
}
عودة NUM ؛
}

نسخة الكود كما يلي:
الطبقة العامة Zhaoqian
{
الفراغ الثابت العام (سلسلة [] args)
{
int m [] = {25،10،5،1} ؛
int n = 99 ؛
int [] num = new int [m.length] ؛
num = Zhaoqian (m ، n) ؛
System.out.println (n+"خطة تقديم المال:") ؛
لـ (int i = 0 ؛ i <m.length ؛ i ++)
System.out.println (num <i>+"zip"+m <i>+"value face") ؛
}
int static int [] Zhaoqian (int m [] ، int n)
{
int k = m.length ؛
int [] num = new int [k] ؛
لـ (int i = 0 ؛ i <k ؛ i ++)
{
num <i> = n/m <i> ؛
n = n ٪ m <i> ؛
}
عودة NUM ؛
}
}

ما سبق هو كل محتوى هذه المقالة ، آمل أن تتمكن من إعجابك بها.