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

เนื้อหา

1 ข้อ 1
2 ข้อ 2
3 ข้อ 3
4 ข้อ 4
5 ข้อ 5
6 ข้อ 6
7 ข้อ 7
8 ข้อ 8

ข้อ 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}\,$ โดยที่ค่า แต่ละค่านั้นจะเริ่มวัดจากแหล่งกิโลเมตรที่ 0 คุณสามารถหยุดพักการเดินทางได้โรงแรม $n\,$ โรงแรมนี้เท่านั้น แต่คุณสามารถเลือกได้ว่าจะหยุดพักที่โรงแรมไหน และคุณจะสิ้นสุดการเดินทางที่โรงแรมสุดท้าย ซึ่งตั้งอยู่ที่ตำแหน่ง $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

a_{n}\,

คุณต้องการที่จะเดินทางเป็นระยะทาง 200 กิโลเมตรต่อวัน แต่มันอาจจะเป็นไปไม่ได้ เนื่องจากโรงแรมอาจจะไม่อยู่ห่างกันเท่ากับ 200 กิโลเมตรพอดี ถ้าคุณเดินทางเป็นระยะทางเท่ากับ กิโลเมตรในวันหนึ่ง คุณจะได้รับ penalty เท่ากับ $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

(200-x)^{2}\,

คุณต้องการที่จะวางแผนการเดินทางของคุณให้ได้รับ penalty รวมน้อยที่สุดเท่าที่จะทำได้

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

เฉลย

ข้อ 3

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

ที่ตำแหน่งทีเ่ป็นไปได้ตำแหน่งหนึ่งๆ ยัคโดนัลด์สามารถตั้งสาขาได้อยากมากเพียงสาขาเดียวเท่านั้น โดยหากตั้งสาขาที่ตำแหน่ง แล้วยัคโดนัลด์จะได้กำไรโดยเฉลี่ยต่อวันเท่ากับ $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } } Error Too many requests (f061ab2) If you report this error to the Wikimedia System Administrators, please include the details below. Request served via cp5021 cp5021, Varnish XID 941399440 Upstream caches: cp5021 int Error: 429, Too many requests (f061ab2) at Tue, 21 Apr 2026 00:26:22 GMT Sensitive client information IP address: 158.108.32.49$ โดยที่ $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } } Error Too many requests (f061ab2) If you report this error to the Wikimedia System Administrators, please include the details below. Request served via cp5021 cp5021, Varnish XID 936518716 Upstream caches: cp5021 int Error: 429, Too many requests (f061ab2) at Tue, 21 Apr 2026 00:26:10 GMT Sensitive client information IP address: 158.108.32.49$ สำหรับ $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } } Error Too many requests (f061ab2) If you report this error to the Wikimedia System Administrators, please include the details below. Request served via cp5021 cp5021, Varnish XID 958531325 Upstream caches: cp5021 int Error: 429, Too many requests (f061ab2) at Tue, 21 Apr 2026 00:26:23 GMT Sensitive client information IP address: 158.108.32.49$
สาขาสองสาขาควรจะอยู่ห่างกันอย่างน้อย $k\,$ กิโลเมตร โดยที่ $k\,$ เป็นจำนวนเต็มบวก

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

เฉลย

ข้อ 4

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

จงใช้ dynamic programming ออกแบบอัลกอริทึตรวจสอบว่าสตริง $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } } Error Too many requests (f061ab2) If you report this error to the Wikimedia System Administrators, please include the details below. Request served via cp5021 cp5021, Varnish XID 962429687 Upstream caches: cp5021 int Error: 429, Too many requests (f061ab2) at Tue, 21 Apr 2026 00:26:11 GMT Sensitive client information IP address: 158.108.32.49$ เกิดจากการนำคำในดิกชันนารีมาเรียงกันหรือไม่ อัลกอริทึมของคุณควรจะทำงานได้ในเวลา $O(n^{2})\,$ หากการเรียก ใช้เวลา
หากสตริงที่ให้มาเกิดจากการเอาคำในดิกชันนารีมาเรียงกันจริงๆ จงออกแบบอัลกอริทึมเพื่อหาลำดับของคำดังกล่าวด้วย

เฉลย

ข้อ 5

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

	$Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } } Error Too many requests (f061ab2) If you report this error to the Wikimedia System Administrators, please include the details below. Request served via cp5021 cp5021, Varnish XID 956042146 Upstream caches: cp5021 int Error: 429, Too many requests (f061ab2) at Tue, 21 Apr 2026 00:26:11 GMT Sensitive client information IP address: 158.108.32.49$
	$b\,$	$b\,$
$b\,$		$b\,$
$c\,$		$c\,$	$c\,$

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

จงออกแบบอัลกอริ่ทึมที่ตรวจสอบว่าสตริงของตัวอักษรทั้งสามตัวข้างบนนี้ ยกตัวอย่างเช่น $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

bbbbac\,

สามารถถูกจัดวงเล็บให้เมื่อทำการคูณออกมาแล้วได้ผลลัพธ์เป็น

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 ไม่ใช่พาลินโีดรม)

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

เฉลย

ข้อ 7

กำหนดสตริง $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

x=x_{1}x_{2}\dotsb x_{n}\,

และ

Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } } Error Too many requests (f061ab2) If you report this error to the Wikimedia System Administrators, please include the details below. Request served via cp5021 cp5021, Varnish XID 958630309 Upstream caches: cp5021 int Error: 429, Too many requests (f061ab2) at Tue, 21 Apr 2026 00:26:15 GMT Sensitive client information IP address: 158.108.32.49

เราต้องการหาความยาวของลำดับร่วมที่มีความยาวมากที่สุด (longest common subsequence) กล่าวคือ จำนวนเต็ม ที่มีค่ามากที่สุดที่ทำให้มีดรรชนี และ ที่ทำให้

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

สมมติว่าคุณเหรียญที่มีค่า $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

x_{1},x_{2},x_{3},\ldots ,x_{n}\,

บาท อยู่ชนิืดละเป็นจำนวนมากมายนับไม่ถ้วน คุณต้องการทอนเงินจำนวน บาท กล่าวคือ คุณต้องการหาเซตของเหรียญกลุ่มหนึี่งที่มีผลรวมเท่ากับ

v\,

พอดี การทอนเงินนี้อาจเป็นไปไม่ได้ ยกตัวอย่างเช่น ถ้าคุณมีแค่เหรียญ 5 บาทกับ 10 บาท คุณสามารถทอนเงิน 15 บาทได้ แต่ไม่สามารถทอนเงิน 12 บาทได้ เป็นต้น จงออกแบบอัลกอริทึมที่ใช้เวลาการทำงาน ที่ใช้แก้ปัญหาทางการคำนวณต่อไปนี้

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

เฉลย

@@ แถว 22: / แถว 22: @@
 == ข้อ 3 ==
-[Dasgupta, Papadimitriou, Vazirani 6.3] บัคโดนัลด์ (Yuckdonald's) กำลังวางแผนจะเปิดสาขใหม่บนถนน Quaint Valley Highway (QVH) โดยตำแหน่งในการตั้งสาขาที่เป็นไปได้ทั้งหมดมีอยู่ <math>n \,</math> คำแหน่ง อยู่บนเส้นตรงเส้นหนึ่ง และระยะทางของตำแหน่งเหล่านี้จากจุดเริ่มต้นของ QVH โดยเรียงจากน้อยไปหามาก คือ <math>m_1, m_2, \ldots, m_n \,</math> ตามลำดับ การตั้งสาขาใหม่ของยัคโดนัลด์จะต้องสอดคล้องกับเงื่อนไขต่อไปนี้
+[Dasgupta, Papadimitriou, Vazirani 6.3] บัคโดนัลด์ (Yuckdonald's) กำลังวางแผนจะเปิดสาขาใหม่บนถนน Quaint Valley Highway (QVH) โดยตำแหน่งในการตั้งสาขาที่เป็นไปได้ทั้งหมดมีอยู่ <math>n \,</math> คำแหน่ง อยู่บนเส้นตรงเส้นหนึ่ง และระยะทางของตำแหน่งเหล่านี้จากจุดเริ่มต้นของ QVH โดยเรียงจากน้อยไปหามาก คือ <math>m_1, m_2, \ldots, m_n \,</math> ตามลำดับ การตั้งสาขาใหม่ของยัคโดนัลด์จะต้องสอดคล้องกับเงื่อนไขต่อไปนี้
 * ที่ตำแหน่งทีเ่ป็นไปได้ตำแหน่งหนึ่งๆ ยัคโดนัลด์สามารถตั้งสาขาได้อยากมากเพียงสาขาเดียวเท่านั้น โดยหากตั้งสาขาที่ตำแหน่ง <math>m_i \,</math> แล้วยัคโดนัลด์จะได้กำไรโดยเฉลี่ยต่อวันเท่ากับ  <math>p_i \,</math> โดยที่ <math>p_i > 0 \,</math> สำหรับ <math>i = 1, 2, \ldots, n \,</math>
 * สาขาสองสาขาควรจะอยู่ห่างกันอย่างน้อย <math>k \,</math> กิโลเมตร โดยที่ <math>k \,</math> เป็นจำนวนเต็มบวก
@@ แถว 68: / แถว 68: @@
 จงออกแบบอัลกอริ่ทึมที่ตรวจสอบว่าสตริงของตัวอักษรทั้งสามตัวข้างบนนี้ ยกตัวอย่างเช่น <math>bbbbac \,</math> สามารถถูกจัดวงเล็บให้เมื่อทำการคูณออกมาแล้วได้ผลลัพธ์เป็น <math>a \,</math> ยกตัวเช่น ถ้าอัลกอริทึมของคุณได้รับข้อมูลเข้าเป็น <math>bbbbac \,</math> อัลกอริทึมของคุณควรจะตอบว่า "ใช่" เนื่องจาก <math>((b(bb))(ba))c = a \,</math>
+[[418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต I/เฉลยข้อ 5|เฉลย]]
 == ข้อ 6 ==
@@ แถว 75: / แถว 77: @@
 จงออกแบบอัลกอริทึมที่ เมื่อให้ลำดับมา หาความยาวของลำดับย่อยที่เป็นพาลินโดรมที่ยาวที่สุด อัลกอริทึมของคุณควรจะทำงานได้ในเวลา <math>O(n^2) \,</math>
+[[418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต I/เฉลยข้อ 6|เฉลย]]
 == ข้อ 7 ==
-กำหนดสตริง <math>x = x_1x_2 \dotsb x_n \,</math> และ <math>y =y_1 y_2 \dotsb y_m \,</math> เราต้องการหาความยาวของสับสตริงร่วมที่มีความยาวมากที่สุด (longest common substring) กล่าวคือ จำนวนเต็ม <math>k  \,</math> ที่มีค่ามากที่สุดที่ทำให้มีดรรชนี <math>i_1 < i_2 < \dotsb < i_k \,</math> และ <math>j_1 < j_2 < \dotsb < j_k \,</math> ที่ทำให้ <math>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} \,</math> จงออกแบบอัลกอริทึมสำหรับแก้ปัญหานี้ อัลกอริทึมของคุณควรจะทำงานได้ในเวลา <math>O(mn) \,</math>
+กำหนดสตริง <math>x = x_1x_2 \dotsb x_n \,</math> และ <math>y =y_1 y_2 \dotsb y_m \,</math> เราต้องการหาความยาวของลำดับร่วมที่มีความยาวมากที่สุด (longest common subsequence) กล่าวคือ จำนวนเต็ม <math>k  \,</math> ที่มีค่ามากที่สุดที่ทำให้มีดรรชนี <math>i_1 < i_2 < \dotsb < i_k \,</math> และ <math>j_1 < j_2 < \dotsb < j_k \,</math> ที่ทำให้ <math>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} \,</math> จงออกแบบอัลกอริทึมสำหรับแก้ปัญหานี้ อัลกอริทึมของคุณควรจะทำงานได้ในเวลา <math>O(mn) \,</math>
+[[418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต I/เฉลยข้อ 7|เฉลย]]
 == ข้อ 8 ==
@@ แถว 83: / แถว 91: @@
 # ข้อมูลนำเข้า: <math>x_1, x_2, \ldots, x_n, v \,</math>
 # ข้อมูลส่งออก: "ใช่" ถ้าคุณสามารถทอนเงิน <math>v \,</math> บาทได้โดยใชเหรียญ <math>x_1, \ldots, x_n \,</math> โดยใช้เหรียญชนิดละกี่เหรียญก็ได้ มิเช่นนี้ให้ตอบ "ไม่ใช่"
+[[418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต I/เฉลยข้อ 8|เฉลย]]

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

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

เนื้อหา

ข้อ 1

ข้อ 2

Error

Error

ข้อ 3

ข้อ 4

ข้อ 5

Error

ข้อ 6

ข้อ 7

Error

ข้อ 8

Error

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

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

เนมสเปซ

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

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ