แนวคิดพื้นฐานของการเขียนโปรแกรมแบบไดนามิกคือการย่อยสลายปัญหาที่จะแก้ไขเป็นปัญหาย่อยหลายประการก่อนแก้ไขปัญหาย่อยก่อนและบันทึกการแก้ปัญหาของปัญหาย่อยเหล่านี้ หากคุณต้องการใช้โซลูชันของปัญหาย่อยเหล่านี้ในอนาคตเมื่อแก้ปัญหาย่อยขนาดใหญ่คุณสามารถดึงโซลูชันที่คำนวณได้เหล่านี้โดยตรงเพื่อหลีกเลี่ยงการดำเนินการซ้ำ ๆ วิธีแก้ปัญหาการบันทึก subproblems สามารถกรอกในวิธีการฟอร์มเช่นการบันทึกในอาร์เรย์
ใช้ตัวอย่างที่เป็นประโยชน์เพื่อสะท้อนแนวคิดอัลกอริทึมของการเขียนโปรแกรมแบบไดนามิก - ปัญหาของการเปลี่ยนแปลงเหรียญ
คำอธิบายคำถาม:
สมมติว่ามีหลายเหรียญและมีปริมาณไม่ จำกัด โปรดทราบจำนวนเหรียญขั้นต่ำที่สามารถทำการเปลี่ยนแปลงจำนวนหนึ่งได้ ตัวอย่างเช่นเหรียญหลายประเภทคือ [1, 3, 5], จำนวนเหรียญต่ำสุดที่มีค่าหน้า 2 คือ 2 (1, 1), จำนวนขั้นต่ำของเหรียญที่มีค่าใบหน้า 4 คือ 2 (1, 3) และจำนวนเหรียญต่ำสุดที่มีค่าหน้า 11 คือ 3 (5, 5, 1 หรือ 5, 3)
การวิเคราะห์ปัญหา:
สมมติว่าชุดเหรียญต่าง ๆ เป็นเหรียญอาเรย์ [0, ... , n-1] จากนั้นค้นหาจำนวนเหรียญขั้นต่ำที่มีค่าหน้า k จากนั้นฟังก์ชันการนับและเหรียญเหรียญอาเรย์เป็นไปตามเงื่อนไขนี้:
นับ (k) = min (count (k - coin [0]), ... , count (k - coin [n - 1])) + 1;
และสูตรก่อนหน้านี้จะถือเฉพาะในกรณีที่เงื่อนไข k - เหรียญ [i]> = 0 && k - เหรียญ [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 | เหรียญ 1 3 5 นาที * 0 0 0 0 0 0 0 * 1 1 0 0 1 * 2 2 0 2 * 3 3 1 0 3, 1 * 4 2 2 2 0 2, 2 * 5 3 3 1 3, 3, 1 * 6 2 2 2 2 2, 2, 2, 2
ในที่สุดการใช้งานรหัส Java ที่เฉพาะเจาะจงมีดังนี้:
สาธารณะคงที่ int backtrackingcoin (int [] เหรียญ, int k) {// วิธีการย้อนกลับ + การเขียนโปรแกรมแบบไดนามิกถ้า (เหรียญ == null || coins.length == 0 || k <1) {return 0; } int [] [] matrix = new int [k + 1] [coins.length + 1]; สำหรับ (int i = 1; i <= k; i ++) {สำหรับ (int j = 0; j <coins.length; j ++) {int prek = i - coins [j]; ถ้า (prek> -1) {// เฉพาะเมื่อไม่น้อยกว่า 0 สามารถมี prek ได้ในเมทริกซ์อาร์เรย์และการย้อนรอยสามารถทำได้ เมทริกซ์ [i] [j] = เมทริกซ์ [prek] [coins.length] + 1; // ค่าใบหน้าฉันกำลังย้อนรอยถ้า (เมทริกซ์ [i] [coins.length] == 0 || เมทริกซ์ [i] [j] <matrix [i] เมทริกซ์ [i] [coins.length] = matrix [i] [j]; }}} ส่งคืนเมทริกซ์ [k] [coins.length]; -รหัสได้รับการทดสอบและกรณีทดสอบทั้งหมดที่กำหนดโดยคำถามได้ผ่านไปแล้ว!
สรุป
ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้เกี่ยวกับรหัสการใช้งานการเปลี่ยนเหรียญของการเขียนโปรแกรม Java Dynamic ฉันหวังว่ามันจะเป็นประโยชน์กับทุกคน เพื่อนที่สนใจสามารถอ้างถึงหัวข้ออื่น ๆ ที่เกี่ยวข้องในเว็บไซต์นี้ต่อไป หากมีข้อบกพร่องใด ๆ โปรดฝากข้อความไว้เพื่อชี้ให้เห็น ขอบคุณเพื่อนที่ให้การสนับสนุนเว็บไซต์นี้!