418341 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต I

ข้อ 1

[Dasgupta, Papadimitriou, Vazirani 6.1] ลำดับย่อยที่ติดกันของลำดับ $S\,$ คือสมาชิกกลุ่มหนึ่งของลำดับ $S\,$ ที่อยู่ติดกัน ยกตัวอย่างเช่นถ้า $S\,$ คือลำดับ

5, 15, -30, 10, -5, 40, 10

แล้ว 15, -30, 10 เป็นลำดับย่อยที่ติดกันของ $S\,$ แต่ 5, 15, 40 ไำม่ใช่ จงหาอัลกอริทึมเพื่อแก้ปัญหาทางการคำนวณต่อไปนี้

ข้อมูลเข้า: ลำดับของจำนวน $a_{1},a_{2},\ldots ,a_{n}\,$

ข้อมูลออก: ลำดับย่อยที่ติดกันทีมีผลบวกรวมของตัวเลขที่อยู่ในลำดับย่อยนั้นมากที่สุด (ลำดับที่มีความยาว 0 มีผลบวกรวมเท่ากับ 0)

สำหรับตัวอย่างข้างบน คำตอบคือ 10, -5, 40, 10 ซึ่งมีผลบวกรวมเท่ากับ 55

อัลกอริทึมของคุณควรจะทำงานได้ในเวลา $O(n)\,$

เฉลย

ข้อ 2

[Dasgupta, Papadimitriou, Vazirani 6.2] คุณกำลังจะเดินทางไกลบนถนนยาวเส้ันหนึ่ง คุณเริ่มต้นเดิน ณ หลักกิโลเมตรที่ 0 ริมถนนมีโรงแรมอยู่ $n\,$ โรงแรม ตั้งอยู่ที่ตำแหน่ง $a_{1},a_{2},\ldots ,a_{n}\,$ โดยที่ค่า $a_{i}\,$ แต่ละค่านั้นจะเริ่มวัดจากแหล่งกิโลเมตรที่ 0 คุณสามารถหยุดพักการเดินทางได้โรงแรม $n\,$ โรงแรมนี้เท่านั้น แต่คุณสามารถเลือกได้ว่าจะหยุดพักที่โรงแรมไหน และคุณจะสิ้นสุดการเดินทางที่โรงแรมสุดท้าย ซึ่งตั้งอยู่ที่ตำแหน่ง $a_{n}\,$

คุณต้องการที่จะเดินทางเป็นระยะทาง 200 กิโลเมตรต่อวัน แต่มันอาจจะเป็นไปไม่ได้ เนื่องจากโรงแรมอาจจะไม่อยู่ห่างกันเท่ากับ 200 กิโลเมตรพอดี ถ้าคุณเดินทางเป็นระยะทางเท่ากับ $x\,$ กิโลเมตรในวันหนึ่ง คุณจะได้รับ penalty เท่ากับ $(200-x)^{2}\,$ คุณต้องการที่จะวางแผนการเดินทางของคุณให้ได้รับ penalty รวมน้อยที่สุดเท่าที่จะทำได้

จงออกแบบอัลกอริทึมที่มีประสิทธิภาพสำหรับแก้ปัญหา

เฉลย

ข้อ 3

[Dasgupta, Papadimitriou, Vazirani 6.3] บัคโดนัลด์ (Yuckdonald's) กำลังวางแผนจะเปิดสาขาใหม่บนถนน Quaint Valley Highway (QVH) โดยตำแหน่งในการตั้งสาขาที่เป็นไปได้ทั้งหมดมีอยู่ $n\,$ คำแหน่ง อยู่บนเส้นตรงเส้นหนึ่ง และระยะทางของตำแหน่งเหล่านี้จากจุดเริ่มต้นของ QVH โดยเรียงจากน้อยไปหามาก คือ $m_{1},m_{2},\ldots ,m_{n}\,$ ตามลำดับ การตั้งสาขาใหม่ของยัคโดนัลด์จะต้องสอดคล้องกับเงื่อนไขต่อไปนี้

• ที่ตำแหน่งทีเ่ป็นไปได้ตำแหน่งหนึ่งๆ ยัคโดนัลด์สามารถตั้งสาขาได้อยากมากเพียงสาขาเดียวเท่านั้น โดยหากตั้งสาขาที่ตำแหน่ง $m_{i}\,$ แล้วยัคโดนัลด์จะได้กำไรโดยเฉลี่ยต่อวันเท่ากับ $p_{i}\,$ โดยที่ $p_{i}>0\,$ สำหรับ $i=1,2,\ldots ,n\,$
• สาขาสองสาขาควรจะอยู่ห่างกันอย่างน้อย $k\,$ กิโลเมตร โดยที่ $k\,$ เป็นจำนวนเต็มบวก

จงออกแบบอัลกอริทึมเพื่อคำนวณหาำกำไรเฉลี่ยต่อวันสูงสุดที่ยัคโดนัลด์จะได้จากการตั้งสาขา ณ ตำแหน่งต่างๆ ตามเงื่อนไขข้างบน

เฉลย

ข้อ 4

[Dasgupta, Papadimitriou, Vazirani 6.4] คุณได้รับสตริงความยาว $n\,$ $s[1\ldots n]\,$ ซึ่งคุณคิดว่าเป็นข้อความที่ถูกตัดเครื่องหมายวรรคตอนทิ้งไปทั้งหมด (ยกตัวอย่างเช่น "iwasthebestoftime") คุณต้องการสร้างข้อความเดิมขึ้นมาโดยใช้ดิกชันนารีเป็นตัวช่วย โดยที่ดิกชันนารีนี้มีรูปแบบเป็นฟังก์ชัน $\mathrm {dict} (\cdot )\,$ ซึ่งสำหรับสตริง $w\,$ ใดๆ แล้ว $\mathrm {dict} (w)=1\,$ ถ้า $w\,$ เป็นคำในดิกชันนารีและ $\mathrm {dict} (w)=0\,$ ไมใช่คำในดิกชันนารี

1. จงใช้ dynamic programming ออกแบบอัลกอริทึตรวจสอบว่าสตริง $s[\cdot ]\,$ เกิดจากการนำคำในดิกชันนารีมาเรียงกันหรือไม่ อัลกอริทึมของคุณควรจะทำงานได้ในเวลา $O(n^{2})\,$ หากการเรียก $\mathrm {dict} (\cdot )\,$ ใช้เวลา $O(1)\,$
2. หากสตริงที่ให้มาเกิดจากการเอาคำในดิกชันนารีมาเรียงกันจริงๆ จงออกแบบอัลกอริทึมเพื่อหาลำดับของคำดังกล่าวด้วย

เฉลย

ข้อ 5

[Dasgupta, Papadimitriou, Vazirani 6.6] พิจารณาตารางสูตรคูณของสัญลักษณ์ $a,b,c\,$ ดังต่อไปนี้

	$a\,$	$b\,$	$c\,$
$a\,$	$b\,$	$b\,$	$c\,$
$b\,$	$c\,$	$b\,$	$a\,$
$c\,$	$a\,$	$c\,$	$c\,$

ภายใต้กฏการคูณข้างบนนี้ เราจะได้ว่า $ab=b\,$ และ $ba=c\,$ เป็นต้น

จงออกแบบอัลกอริ่ทึมที่ตรวจสอบว่าสตริงของตัวอักษรทั้งสามตัวข้างบนนี้ ยกตัวอย่างเช่น $bbbbac\,$ สามารถถูกจัดวงเล็บให้เมื่อทำการคูณออกมาแล้วได้ผลลัพธ์เป็น $a\,$ ยกตัวเช่น ถ้าอัลกอริทึมของคุณได้รับข้อมูลเข้าเป็น $bbbbac\,$ อัลกอริทึมของคุณควรจะตอบว่า "ใช่" เนื่องจาก $((b(bb))(ba))c=a\,$

เฉลย

ข้อ 6

ลำดับย่อยของลำดับหนึ่งจะถูกเรียกว่าเป็นพาลินโดรม ถ้าหากเมื่อเราอ่านมันจากทางซ้ายไปทางขวาแล้วเหมือนกันกับอ่านจากทางขวากไปซ้าย ยกตัวอย่างเช่น ในลำดับ

A, C, G, T, G, T, C, A, A, A, A, T, C, G

มีำลำดับย่อยที่เป็นพาลินโดรมอยู่หลายลำดับ เช่น A, C, G, C, A และ A, A, A, A (ในทางกลับกัน A, C, T ไม่ใช่พาลินโีดรม)

จงออกแบบอัลกอริทึมที่ เมื่อให้ลำดับมา หาความยาวของลำดับย่อยที่เป็นพาลินโดรมที่ยาวที่สุด อัลกอริทึมของคุณควรจะทำงานได้ในเวลา $O(n^{2})\,$

เฉลย

ข้อ 7

กำหนดสตริง $x=x_{1}x_{2}\dotsb x_{n}\,$ และ $y=y_{1}y_{2}\dotsb y_{m}\,$ เราต้องการหาความยาวของลำดับร่วมที่มีความยาวมากที่สุด (longest common subsequence) กล่าวคือ จำนวนเต็ม $k\,$ ที่มีค่ามากที่สุดที่ทำให้มีดรรชนี $i_{1}<i_{2}<\dotsb <i_{k}\,$ และ $j_{1}<j_{2}<\dotsb <j_{k}\,$ ที่ทำให้ $x_{i_{1}}=y_{j_{1}},x_{i_{2}}=y_{j_{2}},x_{i_{3}}=y_{j_{3}},\ldots ,x_{i_{k}}=y_{j_{k}}\,$ จงออกแบบอัลกอริทึมสำหรับแก้ปัญหานี้ อัลกอริทึมของคุณควรจะทำงานได้ในเวลา $O(mn)\,$

เฉลย

ข้อ 8

สมมติว่าคุณเหรียญที่มีค่า $x_{1},x_{2},x_{3},\ldots ,x_{n}\,$ บาท อยู่ชนิืดละเป็นจำนวนมากมายนับไม่ถ้วน คุณต้องการทอนเงินจำนวน $v\,$ บาท กล่าวคือ คุณต้องการหาเซตของเหรียญกลุ่มหนึี่งที่มีผลรวมเท่ากับ $v\,$ พอดี การทอนเงินนี้อาจเป็นไปไม่ได้ ยกตัวอย่างเช่น ถ้าคุณมีแค่เหรียญ 5 บาทกับ 10 บาท คุณสามารถทอนเงิน 15 บาทได้ แต่ไม่สามารถทอนเงิน 12 บาทได้ เป็นต้น จงออกแบบอัลกอริทึมที่ใช้เวลาการทำงาน $O(nv)\,$ ที่ใช้แก้ปัญหาทางการคำนวณต่อไปนี้

1. ข้อมูลนำเข้า: $x_{1},x_{2},\ldots ,x_{n},v\,$
2. ข้อมูลส่งออก: "ใช่" ถ้าคุณสามารถทอนเงิน $v\,$ บาทได้โดยใชเหรียญ $x_{1},\ldots ,x_{n}\,$ โดยใช้เหรียญชนิดละกี่เหรียญก็ได้ มิเช่นนี้ให้ตอบ "ไม่ใช่"

เฉลย