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

125.25.244.191 เมื่อ 07:45, 3 ตุลาคม 2552

2009-10-03T07:45:25Z

Aoy เมื่อ 06:52, 3 ตุลาคม 2552

2009-10-03T06:52:58Z

Aoy เมื่อ 06:26, 3 ตุลาคม 2552

2009-10-03T06:26:40Z

Aoy เมื่อ 06:21, 3 ตุลาคม 2552

2009-10-03T06:21:28Z

Aoy เมื่อ 06:19, 3 ตุลาคม 2552

2009-10-03T06:19:50Z

Aoy: หน้าที่ถูกสร้างด้วย 'ให้ $OPT(i,v)\,$ มีค่าเป็น $yes \,$ ถ้าสามารถใช้เหรียญ…'

2009-10-03T06:18:22Z

หน้าที่ถูกสร้างด้วย 'ให้ <math> OPT(i,v)\,</math> มีค่าเป็น <math> yes \,</math> ถ้าสามารถใช้เหรียญ…'

หน้าใหม่

ให้ <math> OPT(i,v)\,</math> มีค่าเป็น <math> yes \,</math> ถ้าสามารถใช้เหรียญ <math> x_1,x_2,...,x_i \,</math> ทอนเงิน <math>v \,</math> บาทได้ หรือมีค่าเป็น <math> no \,</math> ถ้าไม่สามารถใช้เหรียญ <math> x_1,x_2,...,x_i \,</math> ทอนเงิน <math>v \,</math> บาทได้

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

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

กรณีที่มีเหรียญ<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) OR OPT(i,v-x_i) \,</math> ถ้า <math> v \geq x_i \,</math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 07:45, 3 ตุลาคม 2552
แถว 14:		แถว 14:

	เขียนเป็น pseudocode ได้ดังนี้		เขียนเป็น 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>

@@ แถว 9: / แถว 9: @@
 ส่วนกรณีที่มีเหรียญ <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> x_i \,</math> ช่วยในการทอนเงิน <math> v \,</math> บาท ดังนั้นจึงใช้เหรียญที่เหลือคือ <math> x_1,x_2,...,x_{i-1} \,</math> ในการทอนเงิน <math> v \,</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> x_i \,</math> ช่วยในการทอนเงิน แต่สังเกตว่าเราสามารถใช้เหรียญที่ <math> x_i \,</math> นี้มากกว่าหนึ่งครั้งก็ได้ ดังนั้นจำนวนเหรียญจึงไม่ลดลง แต่จำนวนเงินที่เราต้องทอนจะลดลงไปเป็น <math> v-x_i \,</math> เมื่อ <math> x_i \,</math> เป็นมูลค่าของเหรียญที่ <math> i \,</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>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 06:26, 3 ตุลาคม 2552
แถว 8:		แถว 8:

	ส่วนกรณีที่มีเหรียญ <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> 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> x_i \,</math> ช่วยในการทอนเงิน <math> v \,</math> บาท ดังนั้นจึงใช้เหรียญที่เหลือคือ <math> x_1,x_2,...,x_{i-1} \,</math> ในการทอนเงิน <math> v \,</math> บาทเท่าเดิมแทน
		+
		+	ส่วน <math> OPT(i,v-x_i) \,</math> คือการใช้เหรียญที่ <math> x_i \,</math> ช่วยในการทอนเงิน แต่สังเกตว่าเราสามารถใช้เหรียญที่ <math> x_i \,</math> นี้มากกว่าหนึ่งครั้งก็ได้ ดังนั้นจำนวนเหรียญจึงไม่ลดลง แต่จำนวนเงินที่เราต้องทอนจะลดลงไปเป็น <math> v-x_i \,</math> เมื่อ <math> x_i \,</math> เป็นมูลค่าของเหรียญที่ <math> i \,</math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 06:21, 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> 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>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 06:19, 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> OPT(i,0) = yes \,</math>

−	ส่วนกรณีที่มีเหรียญ <math> x_1,x_2,...,x_i \,</math> เหรียญและมีเงินให้ทอน <math> v \,</math> บาท จะได้ว่า <math> OPT(i,v)=OPT(i-1,v) OR 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)\,</math> OR <math> OPT(i,v-x_i) \,</math> ถ้า <math> v \geq x_i \,</math>