การหาผลลัพธ์ค่าเช่าห้างที่ดีที่สุดด้วย Algorithm
0/1 Knapsack Problem
ปัญหา 0/1 Knapsack (ปัญหาถุงเป้) คือปัญหาเชิงคณิตศาสตร์และคอมพิวเตอร์ ที่ถ้ามีสิ่งของหลายอย่าง
โดยที่ของแต่ละชิ้นมีน้ำหนักและมูลค่าแตกต่างกัน แต่กระเป๋าสามารถบรรจุของได้จำกัด เราจะเลือกของชิ้นไหนบ้าง
เพื่อให้มูลค่ารวมสูงสุด โดยไม่ให้น้ำหนักเกิน?
ซึ่งคำว่า 0/1 หมายถึง:
- เลือกของชิ้นนั้น (1)
- หรือไม่เลือกเลย (0) ที่จะไม่มีการแบ่งของเป็นชิ้นย่อยๆ
ตัวอย่างการใช้
โจทย์ : โจรบุกปล้นร้านทองด้วยประเป๋า 1 ใบ และต้องการขโมยทองเพื่อให้ได้กำไรมากที่สุด แต่กระเป๋าที่โจรเอามาสามารถบรรจุ
ได้แค่ 10 กก. ซึ่งมีของที่ขโมยได้ 3 ชิ้น คือ
- A น้ำหนัก 6 กก. มูลค่า 6 ล้านบาท
- B น้ำหนัก 3 กก. มูลค่า 5 ล้านบาท
- C น้ำหนัก 4 กก. มูลค่า 7 ล้านบาท
คำตอบ : โจรจะเลือกของชิ้น A และ C เพราะน้ำหนักรวมไม่เกิน 10 กก. (พอดีเป๊ะ) และยังได้กำไรสูงที่สุดคือ 13 ล้านบาท
ตัวอย่างการประยุกต์ใน "ทางธุรกิจ"
- การเลือกสินค้าเข้าสต๊อก (Inventory Selection)
- การจัดสรรงบประมาณการตลาด (Marketing Budget Allocation)
- การวางแผนขนส่งสินค้า (Logistics Planning)
- บริษัทเช่า Co-Working Space
ในธุรกิจค้าปลีกหรือค้าส่ง บริษัทมีข้อจำกัดด้าน "พื้นที่จัดเก็บ" และ "งบประมาณสำหรับสต๊อกสินค้า" ไม่สามารถนำสินค้าทุกอย่างเข้าสต๊อกได้ทั้งหมดในคราวเดียว ซึ่งต้องเลือกว่าสินค้าไหนควรเข้าสต๊อก เพื่อให้ได้กำไรสูงที่สุด หรือรองรับความต้องการลูกค้าได้มากที่สุดโดยที่ไม่เกินพื้นที่/งบประมาณที่มี
ในโลกธุรกิจ งบประมาณสำหรับทำการตลาด (Marketing Budget) มีจำกัด บริษัทจึงต้องตัดสินใจว่า จะใช้งบที่มีอยู่ กับแคมเปญโฆษณาไหน เพื่อให้ ยอดขายเพิ่มขึ้นมากที่สุด หรือ หรือผลตอบแทนจากการลงทุน (ROI) สูงที่สุด โดยที่การกำหนดคือ "ต้นทุนโฆษณา" และ "ผลตอบแทนคาดหวัง (ยอดขาย/กำไร)"
ในงานโลจิสติกส์ เช่น การส่งสินค้าโดยรถบรรทุกเรือ หรือเครื่องบิน เรามักเผชิญกับข้อจำกัดสำคัญ เช่น : น้ำหนักบรรทุกสูงสุดที่ยานพาหนะรับได้, ปริมาตร/พื้นที่จำกัดในตู้คอนเทนเนอร์, ต้นทุนขนส่งที่คุมอยู่ในงบ ปัญหาคือต้องเลือกว่าจะขนสินค้าไหนไปก่อนเพื่อให้ได้ มูลค่ารวมสูงสุด ในการขนส่งแต่ละครั้ง เพราะไม่สามารถขนทุกอย่างได้หมดในรอบเดียว
ในธุรกิจ Co-Working Space เช่น WeWork, Spaces หรือ Hubba เจ้าของพื้นที่มี "พื้นที่เช่าจำกัด" เช่น 500 ตารางเมตร
หรือมีจำนวน "ห้องทำงาน" จำกัด เช่น 20 ห้อง
แต่ในความเป็นจริง : ลูกค้าแต่ละรายต้องการพื้นที่ต่างกัน เช่น บางทีมอยากได้ห้องใหญ่ บางทีมขอแค่โต๊ะเดียว และ
ลูกค้าแต่ละรายก็ยอมจ่ายเงินไม่เท่ากัน เช่น บริษัทใหญ่จ่ายแพง แต่ใช้พื้นที่เยอะ
ประโยชน์ของ 0/1 Knapsack ใน "ทางธุรกิจ"
0/1 Knapsack Problem ไม่ได้เป็นเพียงปัญหาคณิตศาสตร์เชิงทฤษฎี แต่เป็นหลักคิดที่ทรงพลังในการจัดสรรทรัพยากร,
เพิ่มกำไร, ตัดสินใจอย่างเป็นระบบ และทำให้ธุรกิจวางแผนและปรับตัวได้อย่างมีประสิทธิภาพในโลกจริง
| ประโยชน์ | อธิบาย |
|---|---|
| ใช้ทรัพยากรได้คุ้มค่า | เลือกการใช้พื้นที่, เงิน, เวลา หรือทรัพยากรอื่น ๆ ให้ได้ผลลัพธ์ดีที่สุด |
| ตัดสินใจอย่างมีหลักการ | ลดความเสี่ยงจากการตัดสินใจผิด เพราะคำนวณทุกตัวเลือกมาแล้ว |
| เพิ่มกำไรสูงสุด | เลือกทางเลือกที่คาดว่าจะได้กำไรหรือมูลค่ารวมสูงที่สุด |
| วางแผนล่วงหน้าได้แม่นยำ | สามารถวางกลยุทธ์ล่วงหน้า เช่น การขยายโกดังหรือเพิ่มงบโฆษณา |
| เหมาะกับงานหลายประเภท | ใช้ได้กับโลจิสติกส์, การตลาด, การผลิต, การเงิน ฯลฯ |
Brute Force (Exhaustive Search)
เป็นวิธีการแก้ปัญหาแบบพื้นฐานที่สุดในวงการคอมพิวเตอร์และคณิตศาสตร์ โดยอาศัยแนวคิดว่า
"ลองทุกทางเลือกที่เป็นไปได้ทั้งหมด (exhaustive search) เพื่อหาคำตอบที่ดีที่สุดหรือถูกต้องที่สุด"หรือก็คือ Brute Force จะไม่พยายามหาทางลัด แต่จะใช้พลังในการสำรวจทุกตัวเลือกที่เป็นไปได้โดยตรง
- พิจารณาทุกกรณี (Every Possibility): ลองชุดคำตอบทุกแบบที่สามารถเกิดขึ้นได้
- เปรียบเทียบผลลัพธ์: เก็บคำตอบที่ดีที่สุดที่เจอในบรรดาทางเลือกทั้งหมด
- ไม่เว้นทางลัด: ไม่มีการคาดเดาหรือข้ามตัวเลือก เพราะไม่รู้ว่าคำตอบที่ดีที่สุดอยู่ที่ไหน
หลักการทำงานของ Brute Force
ลองทุกตัวเลือก → ตรวจเงื่อนไข → เก็บคำตอบที่ดีที่สุด → วนไปจนจบ
.png)
หลักการทำงานเริ่มจากการสร้างชุดตัวเลือกทุกรูปแบบที่เป็นไปได้ จากนั้นประเมินแต่ละตัวเลือก
โดยการคำนวณพื้นที่และรายได้รวม แล้วตรวจสอบว่าตรงตามเงื่อนไข เช่น พื้นที่รวมต้องไม่เกินกำหนดหรือไม่
หากตัวเลือกใดผ่านเงื่อนไข จะนำมาเปรียบเทียบกับคำตอบที่ดีที่สุดที่มีอยู่ และอัปเดตหากตัวเลือกใหม่ให้ผลลัพธ์ที่ดีกว่า
กระบวนการนี้จะทำซ้ำไปเรื่อย ๆ จนครบทุกตัวเลือก สุดท้ายจึงได้คำตอบที่ดีที่สุด
โดยข้อดีของ Brute Force คือสามารถหาคำตอบที่ถูกต้องแน่นอนได้
แต่ข้อเสียคือจะใช้เวลาและทรัพยากรมากเมื่อจำนวนตัวเลือกเพิ่มขึ้น
ตัวอย่างการใช้ Brute Force
ห้างสรรพสินค้าแห่งหนึ่งมีพื้นที่รวมจำกัดคือ 500 ตารางเมตร และพื้นที่ถูกแบ่งออกเป็นโซนเล็ก ๆ
โดยมีผู้สนใจเช่า 5 ราย คือ A B C D E ซึ่งแต่ละผู้เช่าต้องการพื้นที่ และมีการเสนอค่าเช่าที่แตกต่างเช่นกัน ดังตารางข้างล่างเป้าหมายคือ เลือกจัดสรรร้านค้าที่จะมาเช่าในพื้นที่จำกัด ให้ได้ "ผลรวมค่าเช่า" มากที่สุด
| ร้านค้า | พื้นที่ที่ต้องการ (ตร.ม.) | ค่าเช่าที่เสนอ (บาท) |
|---|---|---|
| A | 200 | 50,000 |
| B | 300 | 60,000 |
| C | 100 | 20,000 |
| D | 250 | 70,000 |
| E | 150 | 40,000 |
| ชุดร้านค้า | พื้นที่รวม (ตร.ม.) | ค่าเช่ารวม (บาท) | ถูกเงื่อนไขไหม? | อัปเดตคำตอบที่ดีที่สุด |
|---|---|---|---|---|
| A | 200 | 50,000 | ✅ | 50,000 |
| B | 300 | 60,000 | ✅ | 60,000 |
| C | 100 | 20,000 | ✅ | |
| D | 250 | 70,000 | ✅ | 70,000 |
| E | 150 | 40,000 | ✅ | |
| A + B | 500 | 110,000 | ✅ | 110,000 |
| A + C | 300 | 70,000 | ✅ | |
| A + D | 450 | 120,000 | ✅ | 120,000 |
| A + E | 350 | 90,000 | ✅ | |
| B + C | 400 | 80,000 | ✅ | |
| B + D | 550 | (เกิน 500ตร.ม.) | ❌ | |
| B + E | 450 | 100,000 | ✅ | |
| C + D | 350 | 90,000 | ✅ | |
| C + E | 250 | 60,000 | ✅ | |
| D + E | 400 | 110,000 | ✅ | |
| A + B + C | 600 | (เกิน 500ตร.ม.) | ❌ | |
| A + B + D | 750 | (เกิน 500ตร.ม.) | ❌ | |
| A + B + E | 650 | (เกิน 500ตร.ม.) | ❌ | |
| A + C + D | 550 | (เกิน 500ตร.ม.) | ❌ | |
| A + C + E | 450 | 110,000 | ✅ | |
| A + D + E | 600 | (เกิน 500ตร.ม.) | ❌ | |
| B + C + D | 650 | (เกิน 500ตร.ม.) | ❌ | |
| B + C + E | 550 | (เกิน 500ตร.ม.) | ❌ | |
| B + D + E | 700 | (เกิน 500ตร.ม.) | ❌ | |
| C + D + E | 500 | 130,000 | ✅ | 130,000 |
ผลลัพธ์การใช้ Brute Force
จากการใช้ Brute Force ได้มีการเลือกร้าน C D และ E โดยที่ใช้พื้นที่ได้พอดี รวมไปถึงได้รับค่าเช่าในราคาที่สูงที่สุด
พื้นที่รวม : 500 , พื้นที่คงเหลือ : 0 , ค่าเช่ารวม : 130,000
- คำนวณ พื้นที่รวม
- คำนวณ ค่าเช่ารวม
- ตรวจสอบว่าพื้นที่รวม เกิน 500 ตร.ม. หรือไม่
- ถ้าไม่เกิน ➔ ดูว่ารายได้นี้ดีกว่าที่เคยเจอไหม ➔ ถ้าใช่ อัปเดตคำตอบ
Code Algorithm ที่ใช้ในการเปรียบเทียบ
เนื้อหาเกี่ยวกับ Code...
Dynamic Programming (DP)
เป็นเทคนิคการแก้ปัญหาโดยการแบ่งปัญหาใหญ่ให้เล็กลง แล้วบันทึกคำตอบของปัญหาย่อยเอาไว้ เพื่อลดการคำนวณซ้ำ ๆ
เวลาปัญหาหนึ่ง ๆ ต้อง "คำนวณซ้ำแล้วซ้ำอีก" ในส่วนย่อย ๆ Dynamic Programming จะบอกว่า :
- "ครั้งที่แล้วแก้ปัญหานี้ได้คำตอบอะไรไว้ จำเอาไว้"
- "เวลาเจอปัญหาย่อยเดิมอีก → เอาคำตอบที่จำไว้มาใช้เลย ไม่ต้องคิดใหม่"
หรือก็คือ ถ้าเคยคำนวณผลลัพธ์ของปัญหาเล็ก ๆ ไปแล้ว ก็อย่าคำนวณใหม่ ให้เอาผลลัพธ์เดิมมาใช้เลย
แบบนี้ทำให้ประหยัดทั้ง เวลา และ พลังคำนวณ
หลักการทำงานของ Bottom-Up DP
คือการค่อย ๆ สร้างคำตอบที่ดีที่สุดจากปัญหาย่อยเล็กที่สุด
แล้วค่อย ๆ ขยายขึ้นจนได้คำตอบใหญ่สุด โดยจำค่าที่ดีที่สุดเอาไว้
.png)
START
- Initialize DP Table
- For Each Item (i)
- For Each Capacity (w)
- Update DP[i][w]
- Finish Iterating?
- For Each (i+1) or (w+1)
- Finish Filling Table
- Traceback to Find Selected Items
สร้างตาราง db [ i ][ w ] ขึ้นมา โดยที่ i = ลำดับ w = ข้อมูลเชิงปริมาณ และกำหนดให้ทุกช่อง
เริ่มต้นเป็น 0 (ยังไม่มีรายการที่เลือก)
วนพิจารณาค่า i แต่ละลำดับ เช่น 1-6 ซึ่งแต่ละ i มีข้อมูลเชิงปริมาณ (w) ที่แตกต่างกัน
วนพิจารณาค่า w แต่ละลำดับ เช่น 1-1,000 โดยมีแถวคิดที่ว่า
"ถ้ามีข้อมูล w เท่านี้ จะเลือกหรือไม่เลือก i ดี?"
ขั้นตอนนี้มีความสำคัญตรงที่ต้องคิดว่า จะเลือกหรือไม่เลือก แล้วนำผลลัพธ์ที่ดีที่สุด มาใส่ใน db [ i ][ w ]
- ถ้าไม่เลือก i : db [ i ][ w ] = dp [ i-1 ][ w ] คือการเอาค่าจากตารางเดิมมา (ผลลัพธ์เหมือนเดิม)
- เลือก i ถ้า w ใหญ่พอ : db [ i ][ w ] = db [ i-1 ][ w - limit(w) ] + ข้อมูลเสริม
คือถ้าเลือก i แล้วเหลือ limit(w) เท่าไหร่ และได้ผลลัพธ์ที่ดีที่สุดหรือไม่
ทุกครั้งหลังจากเสร็จขั้นตอน Update db [ i ][ w ] จะเช็คว่า i ครบแล้วยัง หรือ W ดีที่สุดแล้วยัง
ถ้ายังไม่ครบ ไปต่อขั้นตอน For Each (i+1) or (w+1) แต่ถ้าครบแล้ว ไปต่อขั้นตอน Finish Filling Table
- ถ้า w ยังไม่ถึง limit(w) จะเพิ่ม w ไปทีละ 1
- ถ้า w ครบ limit(w) หรือเพิ่มไม่ได้แล้ว จะขยับ i ไปยังลำดับถัดไป
จากนั้นจะวนกลับไปขั้นตอน Update db [ i ][ w ]
เมื่อวนครบทุกตัว ในตารางจะเก็บค่า db [ i ][ w ] ที่ได้ผลลัพธ์ที่ดีที่สุดเอาไว้แล้ว
ซึ่งตารางช่องสุดท้ายของ db [ i ][ w ] จะแสดงผลลัพธ์ที่ดีที่สุด
ในขั้นตอนนี้ จะย้อนกลับไปดูตาราง dp จากช่องสุดท้าย ว่าต้องเลือก i ตัวไหนบ้างที่ให้ผลลัพธ์ที่ดีที่สุด
ถ้า db [ i ][ w ] != dp [ i-1 ][ w ] แปลว่าลำดับที่ i ถูกเลือก แล้วไปลด w ตาม limit(w) ของข้อมูลนั้น
และทำแบบนี้จนรู้ว่าต้องเลือกร้านอะไรบ้าง
END
.png)
ตัวอย่างการใช้ Bottom-Up DP
(กรณีเดียวกัน) ห้างสรรพสินค้าแห่งหนึ่งมีพื้นที่รวมจำกัดคือ 500 ตารางเมตร และพื้นที่ถูกแบ่งออกเป็นโซนเล็ก ๆ
โดยมีผู้สนใจเช่า 5 ราย คือ A B C D E ซึ่งแต่ละผู้เช่าต้องการพื้นที่ และมีการเสนอค่าเช่าที่แตกต่างเช่นกัน ดังตารางข้างล่างเป้าหมายคือ เลือกจัดสรรร้านค้าที่จะมาเช่าในพื้นที่จำกัด ให้ได้ "ผลรวมค่าเช่า" มากที่สุด
| ร้านค้า | พื้นที่ที่ต้องการ (ตร.ม.) | ค่าเช่าที่เสนอ (บาท) |
|---|---|---|
| A | 200 | 50,000 |
| B | 300 | 60,000 |
| C | 100 | 20,000 |
| D | 250 | 70,000 |
| E | 150 | 40,000 |
ขั้นตอนของ Bottom-up DP (พื้นที่จำกัด 500 ตร.ม.)
- สร้างตาราง dp [ i ][ w ] คือ "รายได้สูงสุด" ที่สามารถทำได้
- พิจารณาร้านค้า [ i ] และพื้นที่ที่ต้องการ [ w ]
- ตัดสินใจว่าเลือกหรือไม่เลือก
- เช็คว่าพิจารณาครบหมดแล้วรึยัง
- ได้ผลลลัพธ์ค่าเช่าที่สูงที่สุด
- ตัดสินใจว่าควรเลือกร้านไหนบ้าง เพื่อให้ได้ค่าเช่าที่สูงที่สุด
| ร้านค้า (i) / พื้นที่ (w) |
0 | 100 | 150 | 200 | 250 | 300 | 350 | 400 | 450 | 500 |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 (เริ่มต้น) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 (A) | 0 | 0 | 0 | 50000 | 50000 | 50000 | 50000 | 50000 | 50000 | 50000 |
| 2 (B) | 0 | 0 | 0 | 50000 | 50000 | 60000 | 60000 | 60000 | 60000 | 110000 |
| 3 (C) | 0 | 20000 | 20000 | 50000 | 50000 | 70000 | 70000 | 80000 | 80000 | 110000 |
| 4 (D) | 0 | 20000 | 20000 | 50000 | 70000 | 70000 | 90000 | 90000 | 120000 | 120000 |
| 5 (E) | 0 | 20000 | 40000 | 50000 | 70000 | 70000 | 90000 | 110000 | 120000 | 130000 |
ผลลัพธ์การใช้ DP
จากการใช้ DP ได้มีการเลือกร้าน C D และ E โดยที่ใช้พื้นที่ได้พอดี รวมไปถึงได้รับค่าเช่าในราคาที่สูงที่สุด
พื้นที่รวม : 500 , พื้นที่คงเหลือ : 0 , ค่าเช่ารวม : 130,000ซึ่งจะเห็นได้ว่า ผลลัพธ์เหมือนกันกับการใช้ Brute Force แต่ต่างกันตรงที่วิธีการและความเร็วในการคำนวณ
Code ของฉัน
โค้ดอัลกอริธึมของฉัน...
เปรียบเทียบระหว่าง Brute Force กับ DP
- Brute Force : ต้องลองเลือก "ทุก subset ของร้านค้า" (เช่นเลือก/ไม่เลือกทุกร้านไปเรื่อย ๆ)
- Dynamic Programming : จำผลลัพธ์ย่อยเอาไว้, ไม่ต้องทำซ้ำซ้อน → เร็วกว่าหลายสิบหลายร้อยเท่า
| ประเด็น | Brute Force | Dynamic Programming |
|---|---|---|
| วิธีทำงาน | ลอง "ทุกรูปแบบที่เป็นไปได้" | ใช้การ "จำคำตอบย่อย" (memoization) มาต่อกัน |
| จำนวนคำตอบที่ต้องเช็ค | 2^n กรณี | n×w กรณี |
| เวลาทำงาน (Time Complexity) | O(2^n) | O(n×w) |
| หน่วยความจำที่ใช้ (Memory) | น้อย (แต่แลกกับช้า) | ต้องใช้ตาราง DP (พื้นที่มากขึ้นนิดนึง) |
| ข้อเสีย | ช้ามากเมื่อจำนวนร้านเพิ่มขึ้น | ใช้ memory เพิ่ม แต่ยังคุ้มถ้า w ไม่ใหญ่มาก |
สรุปว่าทำไม DP ดีกว่า Brute Force
ในการแก้ปัญหาการเลือกพื้นที่ให้เช่าภายในห้างสรรพสินค้า เพื่อให้ได้รายได้ค่าเช่าสูงสุดภายใต้ข้อจำกัดด้านพื้นที่ การเลือกวิธีการแก้ปัญหาที่มีประสิทธิภาพ ค่อนข้างมีความสำคัญ เนื่องจากจำนวนตัวเลือก (ร้านค้า) ที่เพิ่มขึ้นเพียงเล็กน้อย อาจทำให้เวลาคำนวณเพิ่มขึ้นอย่างมหาศาลได้
สองแนวทางหลักที่สามารถใช้แก้ปัญหานี้ได้คือ Brute Force และ Dynamic Programming (DP) ซึ่งเมื่อนำมาเปรียบเทียบกัน จะเห็นได้อย่างชัดเจนว่า Dynamic Programming มีข้อได้เปรียบเหนือ Brute Force หลายประการ ดังนี้
- ความเร็วในการทำงานที่เหนือกว่า
- ประหยัดการคำนวณซ้ำซ้อน
- รองรับการขยายขนาดข้อมูล
- ความสามารถในการใช้งานจริง
| Algorithm | Run time (ms) |
|---|---|
| Brute Force | - |
| Dynamic Programming (DP) | - |
ไฟล์ .txt ของตัวเลขพื้นที่ที่ต้องการ และค่าเช่าที่เสนอ (กรณี 20 ร้าน)
วิดีโออธิบายหลักการทำงาน
