DP แบบไม่จำกัดจำนวนและการทอนเหรียญ
ใช้สมาชิกแต่ละรายการได้กี่ครั้งก็ได้
DP แบบไม่จำกัดจำนวนและการทอนเหรียญ เป็นบทเรียน Competitive Programming Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Competitive Programming Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
สิ่งของที่ใช้ได้ไม่จำกัด
ในปัญหา กระเป๋าแบบไม่จำกัดจำนวนครั้ง คุณสามารถเลือกสิ่งของแต่ละชิ้นได้มากเท่าที่ต้องการ ลองนึกถึงเหรียญในตู้จำหน่ายสินค้า ไม่ใช่กองสิ่งของที่มีจำนวนจำกัด
การเปลี่ยนแปลงเล็กน้อยเพียงจุดเดียว
เมื่อเทียบกับแบบ 0/1 มีเพียงทิศทางการวนที่เปลี่ยนไป สำหรับสิ่งของที่ใช้ได้ไม่จำกัด ให้วนความจุไปข้างหน้า จากค่าต่ำไปค่าสูง
การนำกลับมาใช้ซ้ำแบบเดินหน้าคือหัวใจสำคัญ
เมื่อวนไปข้างหน้า dp[w - coin] อาจรวมสิ่งของชิ้นเดียวกันนี้ไว้แล้ว การ นำกลับมาใช้ซ้ำ โดยตั้งใจนี้เองที่ทำให้คุณเลือกสิ่งของนั้นได้อีกครั้ง
มารู้จักปัญหาการทอนเหรียญ
ปัญหา การทอนเหรียญ แบบคลาสสิกถามหาจำนวนเหรียญน้อยที่สุดที่รวมกันได้จำนวนเงินหนึ่งค่า นี่คือ DP แบบไม่จำกัดจำนวนครั้งที่ใช้ค่าต่ำสุดแทนค่าสูงสุด
กำหนดสถานะ
ให้ dp[a] เป็นจำนวนเหรียญน้อยที่สุดที่ต้องใช้เพื่อสร้างจำนวนเงิน a เริ่มต้นด้วย dp[0] = 0 เพราะศูนย์ไม่ต้องใช้เหรียญ
dp = [float("inf")] * (amount + 1)
dp[0] = 0ใช้อนันต์แทนค่าที่เป็นไปไม่ได้
ให้จำนวนเงินที่ไปไม่ถึงเริ่มต้นด้วยค่า อนันต์ หากจำนวนเงินใดยังคงเป็นอนันต์เมื่อจบการคำนวณ แสดงว่าไม่สามารถสร้างจำนวนนั้นจากชุดเหรียญใดได้
การเปลี่ยนสถานะ
สำหรับเหรียญแต่ละเหรียญ ให้ลองปรับปรุงจำนวนเงินทุกค่าที่เหรียญนั้นไปถึงได้ โดยใช้จำนวนเหรียญมากกว่าจำนวนเงินที่ น้อยกว่า ซึ่งเหลืออยู่หนึ่งเหรียญ
for coin in coins:
for a in range(coin, amount + 1):
dp[a] = min(dp[a], dp[a - coin] + 1)เหตุใดจึงต้องวนไปข้างหน้า
การกวาดจำนวนเงินจากน้อยไปมากทำให้ dp[a - coin] อาจนับเหรียญนี้ไว้แล้ว นี่คือวิธีที่เหรียญเดียวกันมีส่วนช่วยได้ หลายครั้ง
นับจำนวนวิธีแทน
เปลี่ยนจาก min+1 เป็นผลรวมเพื่อนับจำนวน วิธีในการสร้างจำนวนเงินแต่ละค่า การวางรอบเหรียญไว้ด้านนอกช่วยป้องกันการนับลำดับซ้ำสองครั้ง
for coin in coins:
for a in range(coin, amount + 1):
dp[a] += dp[a - coin]อ่านผลลัพธ์
คำตอบอยู่ใน dp[amount] สำหรับรูปแบบหาค่าต่ำสุด ค่าที่เป็นอนันต์หมายความว่าไม่สามารถสร้างจำนวนเงินเป้าหมายได้
0/1 กับแบบไม่จำกัดจำนวนครั้ง
จำสวิตช์เดียวนี้ไว้: การวนความจุแบบ ย้อนกลับ หมายถึงใช้สิ่งของแต่ละชิ้นได้ครั้งเดียว ส่วนการวนไปข้างหน้าหมายถึงใช้ได้ไม่จำกัด ตารางเหมือนเดิม แต่กวาดคนละทิศทาง
ตรวจสอบอย่างรวดเร็ว
ทดสอบว่าอะไรทำให้ปัญหากระเป๋าเป็นแบบไม่จำกัดจำนวนครั้ง
ทบทวน
คุณเปลี่ยนรอบวนซ้ำให้เดินหน้าเพื่อรองรับการใช้ซ้ำได้ไม่จำกัด และสร้างปัญหาการทอนเหรียญด้วยการใช้ค่าต่ำสุดเพื่อหาจำนวนเหรียญน้อยที่สุด หรือใช้ผลรวมเพื่อหาจำนวน วิธีทั้งหมด 💰
คำถามที่พบบ่อย
บทเรียน “DP แบบไม่จำกัดจำนวนและการทอนเหรียญ” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “DP แบบไม่จำกัดจำนวนและการทอนเหรียญ” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Competitive Programming Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “DP แบบไม่จำกัดจำนวนและการทอนเหรียญ”
ใช้สมาชิกแต่ละรายการได้กี่ครั้งก็ได้ คุณปฏิบัติ Competitive Programming Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Competitive Programming Academy หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Competitive Programming Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน
บทเรียน “DP แบบไม่จำกัดจำนวนและการทอนเหรียญ” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Competitive Programming Academy นี้ได้ไหม
ได้ บทเรียน Competitive Programming Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- กระเป๋า 0/1: เลือกหรือไม่เลือก
- กระเป๋าที่ปรับปรุงการใช้พื้นที่
- DP แบบไม่จำกัดจำนวนและการทอนเหรียญ
- ผลรวมเซตย่อยและการแบ่งส่วน