ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต I/เฉลยข้อ 8"

รุ่นแก้ไขปัจจุบันเมื่อ 07:45, 3 ตุลาคม 2552

ให้ $OPT(i,v)\,$ มีค่าเป็น $yes\,$ ถ้าสามารถใช้เหรียญ $x_{1},x_{2},...,x_{i}\,$ ทอนเงิน $v\,$ บาทได้ หรือมีค่าเป็น $no\,$ ถ้าไม่สามารถใช้เหรียญ $x_{1},x_{2},...,x_{i}\,$ ทอนเงิน $v\,$ บาทได้

พิจารณากรณีที่ไม่มีเหรียญและไม่มีเงินต้องทอน จะได้ว่า $OPT(0,0)=yes\,$

กรณีที่ไม่มีเหรียญแต่มีเงินให้ทอน $v\,$ บาทจะได้ว่า $OPT(0,v)=no\,$ ถ้า $v>0\,$

กรณีที่มีเหรียญ $x_{1},x_{2},...,x_{i}\,$ เหรียญแต่ไม่มีเงินให้ทอน จะได้ว่า $OPT(i,0)=yes\,$

ส่วนกรณีที่มีเหรียญ $x_{1},x_{2},...,x_{i}\,$ เหรียญและมีเงินให้ทอน $v\,$ บาท จะได้ว่า $OPT(i,v)=OPT(i-1,v)\vee OPT(i,v-x_{i})\,$ ถ้า $v\geq x_{i}\,$

อธิบายเพิ่ม $OPT(i-1,v)\,$ คือการที่ไม่ใช้เหรียญ $i\,$ ช่วยในการทอนเงิน $v\,$ บาท ดังนั้นจึงใช้เหรียญที่เหลือคือ $1,2,...,(i-1)\,$ ในการทอนเงิน $v\,$ บาทเท่าเดิมแทน

ส่วน $OPT(i,v-x_{i})\,$ คือการใช้เหรียญที่ $i\,$ ช่วยในการทอนเงิน แต่สังเกตว่าเราสามารถใช้เหรียญที่ $i\,$ นี้มากกว่าหนึ่งครั้งก็ได้ ดังนั้นจำนวนเหรียญที่จะใช้ทอนเงินจึงไม่ลดลง แต่จำนวนเงินที่เราต้องทอนจะลดลงไปเป็น $v-x_{i}\,$ เมื่อ $x_{i}\,$ เป็นมูลค่าของเหรียญที่ $i\,$

เขียนเป็น pseudocode ได้ดังนี้

<geshi lang="c"> FindSolution(i,v)

   if i=0 and v=0 then
       return 1
   else if i=0 and v > 0 then
       return 0
   else if v=0 then 
       return 1
   else 
       if v >= x_i
           M(i,v)= FindSolution(i-1,v) OR FindSolution(i,v-x_i)
   return M(i,v)

</geshi>

ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต I/เฉลยข้อ 8"

รุ่นแก้ไขปัจจุบันเมื่อ 07:45, 3 ตุลาคม 2552

รายการเลือกการนำทาง

เครื่องมือส่วนตัว

เนมสเปซ

สิ่งที่แตกต่าง

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ

@@ แถว 7: / แถว 7: @@
 กรณีที่มีเหรียญ<math> x_1,x_2,...,x_i \,</math> เหรียญแต่ไม่มีเงินให้ทอน จะได้ว่า  <math> OPT(i,0) = yes \,</math>
-ส่วนกรณีที่มีเหรียญ <math> x_1,x_2,...,x_i \,</math> เหรียญและมีเงินให้ทอน <math> v \,</math> บาท จะได้ว่า <math> OPT(i,v)=OPT(i-1,v)\,</math> OR <math> OPT(i,v-x_i) \,</math> ถ้า <math> v \geq x_i \,</math>
+ส่วนกรณีที่มีเหรียญ <math> x_1,x_2,...,x_i \,</math> เหรียญและมีเงินให้ทอน <math> v \,</math> บาท จะได้ว่า <math> OPT(i,v)=OPT(i-1,v) \vee OPT(i,v-x_i) \,</math> ถ้า <math> v \geq x_i \,</math>
+อธิบายเพิ่ม <math> OPT(i-1,v)\,</math> คือการที่ไม่ใช้เหรียญ <math> i \,</math> ช่วยในการทอนเงิน <math> v \,</math> บาท ดังนั้นจึงใช้เหรียญที่เหลือคือ <math> 1,2,...,(i-1) \,</math> ในการทอนเงิน <math> v \,</math> บาทเท่าเดิมแทน
+ส่วน <math> OPT(i,v-x_i) \,</math> คือการใช้เหรียญที่ <math> i \,</math> ช่วยในการทอนเงิน แต่สังเกตว่าเราสามารถใช้เหรียญที่ <math> i \,</math> นี้มากกว่าหนึ่งครั้งก็ได้ ดังนั้นจำนวนเหรียญที่จะใช้ทอนเงินจึงไม่ลดลง แต่จำนวนเงินที่เราต้องทอนจะลดลงไปเป็น <math> v-x_i \,</math> เมื่อ <math> x_i \,</math> เป็นมูลค่าของเหรียญที่ <math> i \,</math>
+เขียนเป็น pseudocode ได้ดังนี้
+<geshi lang="c">
+FindSolution(i,v)
+    if i=0 and v=0 then
+        return 1
+    else if i=0 and v > 0 then
+        return 0
+    else if v=0 then
+        return 1
+    else
+        if v >= x_i
+            M(i,v)= FindSolution(i-1,v) OR FindSolution(i,v-x_i)
+    return M(i,v)
+</geshi>