Coin Change
การทอนเหรียญและจำนวนวิธี
Knapsack
การเลือกสิ่งของภายใต้ข้อจำกัด
LIS
ลำดับย่อยที่ยาวที่สุด
• **เป็นรากฐานของโจทย์ซับซ้อน**: โจทย์ในการแข่งขันส่วนใหญ่คือการดัดแปลงจากโจทย์มาตรฐานเหล่านี้
• **ครอบคลุมมิติของสถานะ (States)**: มีทั้งแบบ 1 มิติ (Coin) และ 2 มิติ (Knapsack)
• **แสดงจุดอ่อนของ Greedy**: โจทย์เหล่านี้พิสูจน์ว่าทำไมการเลือกแบบเฉพาะหน้าถึงไม่ได้คำตอบที่ดีที่สุดเสมอไป
• **เทคนิคการประหยัดพื้นที่**: เรียนรู้วิธีลดหน่วยความจำจาก \(O(N)\) เหลือ \(O(1)\) หรือจาก \(O(N^2)\) เหลือ \(O(N)\)
มีชุดเหรียญ \(coins = \{c_1, c_2, ..., c_k\}\) ต้องการรวมให้ได้มูลค่า \(n\) โดยใช้จำนวนเหรียญ **น้อยที่สุด**
Greedy Approach (Fail Case):
Coins: {1, 3, 4}, Target: 6
• Greedy: 4 + 1 + 1 (3 เหรียญ)
• Optimal: 3 + 3 (2 เหรียญ)
DP Approach:
ตรวจสอบทุกทางเลือกที่เป็นไปได้ และจดจำคำตอบที่ดีที่สุดของแต่ละมูลค่าไว้
\(solve(x) = \min_{c \in coins}(solve(x-c) + 1)\)
• **\(solve(x)\)**: จำนวนเหรียญที่น้อยที่สุดที่รวมกันได้ \(x\)
• **Base Case**: \(solve(0) = 0\) (มูลค่า 0 ใช้ 0 เหรียญ)
• **Infinite Case**: \(solve(x < 0) = \infty\) (มูลค่าติดลบเป็นไปไม่ได้)
• **Transitions**: ในแต่ละสถานะ เราลองหยิบเหรียญที่มีทุกลูก และไปเรียกปัญหาย่อยที่เหลือ
// ไม่มีการจดจำค่า ทำให้เกิดการคำนวณซ้ำมหาศาล
int solve(int x) {
if (x < 0) return INF;
if (x == 0) return 0;
int best = INF;
for (auto c : coins) {
best = min(best, solve(x-c) + 1);
}
return best;
}
⚠️ สำหรับ \(x\)ขนาดใหญ่ ฟังก์ชันนี้จะค้างเพราะความซับซ้อนระดับ \(O(k^n)\)
value = 0;
for (int x = 1; x <= n; x++) {
value[x] = INF;
for (auto c : coins) {
if (x-c >= 0) {
value[x] = min(value[x], value[x-c]+1);
}
}
}
Complexity: \(O(n \cdot k)\)
ใช้ตาราง first[x] เพื่อจำว่าเหรียญใดถูกเลือกเป็นตัวแรกที่ทำให้ได้ค่าเหมาะสมที่สุด
// ขณะเติมตาราง DP
if (value[x-c]+1 < value[x]) {
value[x] = value[x-c]+1;
first[x] = c;
}
// การดึงคำตอบกลับ
while (n > 0) {
cout << first[n] << " ";
n -= first[n];
}
โจทย์ถาม: มีวิธีรวมเงินให้ได้ \(x\) ทั้งหมด **กี่วิธี?**
เปลี่ยนจากการหาค่าต่ำสุด (\(\min\) เป็นการรวมผลลัพธ์ (\(\sum\)) จากสถานะย่อยทั้งหมด
**หมายเหตุ**: ระวังปัญหาเรื่องลำดับ (Order) หากต้องการนับ Combinations แทนที่จะเป็น Permutations
ในโจทย์การนับ (Counting) จำนวนวิธีมักจะมีค่ามหาศาลเกินกว่าจะเก็บใน long long ได้ โจทย์จึงมักให้ตอบแบบ **Modulo \(10^9+7\)**
count[x] += count[x-c];
count[x] %= 1000000007;
"จงจำไว้ว่าต้องทำ Modulo ในทุกขั้นตอนการบวกเพื่อความถูกต้อง"
"การบรรจุของลงย่ามเพื่อให้ได้มูลค่าสูงสุด"
• 0/1 Knapsack: ของแต่ละชิ้นเลือกได้เพียงครั้งเดียว (หยิบหรือไม่หยิบ)
• **Unbounded Knapsack**: ของแต่ละชิ้นเลือกกี่ครั้งก็ได้
• **Bounded Knapsack**: มีจำนวนจำกัดสำหรับของแต่ละชนิด
\(K(c, i)\) = มูลค่าสูงสุดเมื่อใช้ความจุ \(c\) และพิจารณาของ \(i\) ชิ้นแรก
ความสัมพันธ์เวียนเกิด:
สำหรับการเติมตาราง \(best[n+1][C+1]\) เรามักวนลูปตามจำนวนชิ้นงาน (ของ) ในแถวนอก และวนลูปตามความจุ (Weight) ในแถวใน
| i \ C | 0 | 1 | 2 | ... | W |
|---|---|---|---|---|---|
| ชิ้นที่ 0 | 0 | 0 | 0 | 0 | 0 |
| ชิ้นที่ 1 | 0 | คำนวณตามสูตร max(skip, pick) | |||
* แถวแรกเป็น 0 เสมอ เพราะไม่มีของให้เลือก
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= W; j++) {
dp[i][j] = dp[i-1][j]; // ไม่เลือก
if (j >= weight[i]) {
dp[i][j] = max(dp[i][j], dp[i-1][j-weight[i]] + value[i]);
}
}
}
Complexity: \(O(n \cdot W)\) ทั้งเวลาและพื้นที่
"เราใช้ข้อมูลจากแถวก่อนหน้า (\(i-1\)) เท่านั้น"
เราสามารถลดการใช้พื้นที่จาก \(O(n \cdot W)\) เหลือเพียง **\(O(W)\)** ได้โดยใช้อาเรย์ 1 มิติ
⚠️ ข้อสำคัญ:
ในการวนลูปความจุ (\(j\)) ต้องวนจาก **ขวาไปซ้าย (W ลดลงไป 0)** เพื่อป้องกันไม่ให้เราใช้ของชิ้นเดิมซ้ำในแถวเดียวกัน
int dp[W + 1] = {0};
for (int i = 1; i <= n; i++) {
for (int j = W; j >= weight[i]; j--) {
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
การวนลูปจากขวาไปซ้ายช่วยให้สถานะ dp[j - weight[i]] ยังเป็นค่าจาก "แถวก่อนหน้า" จริงๆ ไม่ใช่ค่าที่ถูกปรับปรุงใหม่ในแถวเดียวกัน
โจทย์: กำหนดน้ำหนัก \([w_1, w_2, ..., w_n]\) สามารถรวมเป็นค่า \(x\) ได้หรือไม่?
เป็น Knapsack รูปแบบหนึ่งที่ Value มีค่าเป็น 0 หรือบูลีน (True/False)
"Possible(x, k) = Possible(x - w_k, k-1) OR Possible(x, k-1)"
Weights: [29-31], Target: 7
ลำดับการสร้าง:
เทคนิค: ใช้ std::bitset ใน C++ เพื่อให้การทำ Subset Sum เร็วขึ้นมหาศาล (\(O(NW/64)\))
เริ่มจากคำตอบที่ได้ใน dp[n][W] แล้วตรวจสอบถอยหลังว่าในโหนดแม่นั้นๆ เรา "หยิบ" หรือ "ไม่หยิบ" ของชิ้นนั้น
เงื่อนไขตรวจสอบ:
อาเรย์: [29-31, 35-39]
LIS: [31, 36, 37, 39] (ความยาว 4)
* หมายเหตุ: ลำดับย่อย (Subsequence) ไม่จำเป็นต้องอยู่ติดกันในอาเรย์ตั้งต้น
\(length(k)\) = ความยาว LIS ที่ **จบลงที่ตำแหน่ง \(k\)**
Recurrence:
1 + max( { length(i) | i < k และ A[i] < A[k] } ∪ {0} )
"เพื่อคำนวณ \(length(k)\) เราย้อนกลับไปมองตำแหน่ง \(i\) ก่อนหน้าทั้งหมดที่ตัวเลขน้อยกว่าตำแหน่งปัจจุบัน แล้วเลือกตัวที่ให้ LIS ยาวที่สุดมาบวกเพิ่ม 1"
for (int k = 0; k < n; k++) {
length[k] = 1; // ค่าตั้งต้น
for (int i = 0; i < k; i++) {
if (array[i] < array[k]) {
length[k] = max(length[k], length[i] + 1);
}
}
}
คำตอบสุดท้ายคือค่าสูงสุดในอาเรย์ length
ขั้นตอน:
parent[k] = i เมื่อมีการเลือกค่าที่เหมาะสมที่สุดlength มากที่สุดparent เพื่อดึงลำดับออกมา"การจดจำทางเลือกช่วยให้เราขยายโจทย์จากการหาความยาว ไปสู่การหาผลลัพธ์ที่เป็นรูปธรรมได้"
ทำไม O(N^2) ถึงไม่พอ?
สำหรับการแข่งขันโอลิมปิกที่ \(N = 10^5\) อัลกอริทึม \(O(N^2)\) จะได้ TLE (Time Limit Exceeded) ทันที
แนวคิด O(N log N):
ใช้อาเรย์เสริมเพื่อเก็บ "ค่าตัวเลขที่น้อยที่สุดที่เป็นไปได้สำหรับการสร้าง LIS ความยาว \(L\)" ร่วมกับการใช้ **Binary Search** เพื่อหาตำแหน่งแทรกที่เหมาะสม
| Problem | Time Complexity | Space Complexity |
|---|---|---|
| Coin Change | \(O(n \cdot k)\) | \(O(n)\) |
| Knapsack (0/1) | \(O(n \cdot W)\) | \(O(W)\) (Optimized) |
| LIS | \(O(n \log n)\) | \(O(n)\) |
ใช้พิจารณาข้อมูลตั้งแต่ต้นจนถึงตำแหน่งปัจจุบัน (เช่น LIS)
ใช้พิจารณาทรัพยากรที่มีจำกัด (เช่น Knapsack, Coin)
พิจารณาส่วนย่อยในช่วง [L, R] ใดๆ
เคลื่อนที่บนตาราง 2 มิติ
"Don't just code, visualize the table!"
ชุดโจทย์มาตรฐาน 26 ข้อ (A-Z) ที่ครอบคลุมทุกเทคนิคพื้นฐานจนถึงขั้นสูง
ส่วนของ Dynamic Programming ที่เน้นโจทย์คลาสสิกที่ทุกโอลิมปิกควรรู้
"ทำไมเราต้องทำ DP ที่ซับซ้อน ในเมื่อ Greedy ดูง่ายกว่า?"
ตรวจสอบจุดบกพร่องดังนี้:
"Dynamic Programming is not hard. It just requires practice."
เราได้ครอบคลุมหัวใจสำคัญของ Coin, Knapsack และ LIS แล้ว. เวลาที่เหลือของวันนี้ (15:00 - 17:00) จะเป็นช่วงเวลาให้คุณได้ลงมือแก้โจทย์จริง!