تتمثل الفكرة الأساسية للبرمجة الديناميكية في تحلل المشكلة التي سيتم حلها في العديد من المشاكل الفرعية ، وحل المشاكل الفرعية أولاً ، وتوفير حلول هذه المشاكل الفرعية. إذا كنت بحاجة إلى استخدام حلول هذه المشاكل الفرعية في المستقبل عند حل المشاكل الفرعية الكبيرة ، فيمكنك استخراج هذه الحلول المحسوبة مباشرة لتجنب العمليات المتكررة. يمكن ملء حل المشكلات الفرعية لتوفير باستخدام طريقة النموذج ، مثل الادخار في صفيف.
استخدم مثالًا عمليًا لتعكس الفكرة الخوارزمية للبرمجة الديناميكية - مشكلة تغيير العملة.
وصف السؤال:
لنفترض أن هناك العديد من العملات المعدنية وهناك كميات غير محدودة. يرجى العثور على الحد الأدنى لعدد العملات المعدنية التي يمكن أن تشكل عددًا معينًا من التغيير. على سبيل المثال ، هناك عدة أنواع من العملات المعدنية [1 ، 3 ، 5] ، والحد الأدنى لعدد العملات المعدنية ذات القيمة الاسمية 2 هو 2 (1 ، 1) ، والحد الأدنى لعدد العملات المعدنية ذات القيمة الاسمية 4 هو 2 (1 ، 3) ، والحد الأدنى لعدد العملات المعدنية ذات القيمة الاسمية 11 هو 3 (5 ، 5 ، 1 أو 5 ، 3 ، 3).
تحليل المشكلة:
افترض أن المجموعات المختلفة من العملات المعدنية هي عملة صفيف [0 ، ... ، N-1]. ثم ابحث عن الحد الأدنى لعدد العملات المعدنية مع القيمة الاسمية K ، ثم تلبي وظيفة Count وعملة المعدلة هذه الحالة:
count (k) = min (count (k - coin [0]) ، ... ، count (k - coin [n - 1])) + 1 ؛
والصيغة السابقة تحمل فقط ما إذا كان الشرط K - Coin [i]> = 0 && k - Coin [i] <K يتم استيفاءه.
لأن K- Coin [i] <k ، عند حساب العد (k) ، يجب أن يتم الوفاء بالعد (i) (i <- [0 ، k-1]) ، لذلك ينطوي هنا على مشكلة التراجع.
حتى نتمكن من إنشاء مصفوفة مصفوفة [K + 1] [Coin.Length + 1] ، بحيث يتم تهيئة المصفوفة [0] [J] إلى 0 قيمًا ، وحفظ الحد الأدنى من العملات المعدنية ذات القيمة الاسمية I في المصفوفة [i] [Coin.Length].
والعملية المحددة هي كما يلي:
* K | Coin 1 3 5 Min * 0 0 0 0 0 0 * 1 1 0 0 1 * 2 2 0 2 * 3 3 1 0 3 ، 1 * 4 2 2 0 2 ، 2 * 5 3 3 1 ، 3 ، 1 * 6 2 2 2 ، 2 ، 2 * ...
أخيرًا ، يكون تطبيق رمز Java المحدد كما يلي:
public static int backtrackingcoin (int [] coins ، int k) {// backtracking method + programming if (coins == null || coins.length == 0 || k <1) {return 0 ؛ } int [] [] matrix = new int [k + 1] [coins.length + 1] ؛ لـ (int i = 1 ؛ i <= k ؛ i ++) {for (int j = 0 ؛ j <coins.length ؛ j ++) {int prek = i - coins [j] ؛ إذا كان (prek> -1) {// فقط عندما لا يكون أقل من 0 ، يمكن أن توجد prek في مصفوفة الصفيف ويمكن تنفيذ التراجع. المصفوفة [i] [j] = matrix [prek] [coins.length] + 1 ؛ // القيمة الاسمية I تتراجع if (matrix [i] [coins.length] == 0 || matrix [i] Matrix [i] [coins.length] = matrix [i] [j] ؛ }}} مصفوفة الإرجاع [k] [coins.length] ؛ }تم اختبار الرمز ، وقد مرت جميع حالات الاختبار التي قدمها السؤال!
لخص
ما سبق هو المحتوى الكامل لهذه المقالة حول رمز تنفيذ مشكلة تغيير العملة للبرمجة الديناميكية Java. آمل أن يكون ذلك مفيدًا للجميع. يمكن للأصدقاء المهتمين الاستمرار في الرجوع إلى الموضوعات الأخرى ذات الصلة على هذا الموقع. إذا كانت هناك أي أوجه قصور ، فيرجى ترك رسالة لإشارةها. شكرا لك يا أصدقائك لدعمكم لهذا الموقع!