0Pricing
Coding Interview Prep · บทเรียน

กระเป๋าเป้ไม่จำกัดจำนวนและการทอนเหรียญ II

อนุญาตให้นำสิ่งของกลับมาใช้ซ้ำด้วยการวนความจุจากน้อยไปมาก แล้วแก้ปัญหาการทอนเหรียญ II (นับจำนวนวิธี) และการตัดแท่งด้วยรูปแบบนี้

กระเป๋าเป้ไม่จำกัดจำนวนและการทอนเหรียญ II เป็นบทเรียน Coding Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Coding Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน

แนวคิดกระเป๋าเป้แบบไม่จำกัด

ในกระเป๋าเป้แบบไม่จำกัด สิ่งของแต่ละชิ้นสามารถเลือกได้กี่ครั้งก็ได้ (ต่างจากกระเป๋าเป้ 0/1 ที่ใช้สิ่งของแต่ละชิ้นได้มากที่สุดหนึ่งครั้ง) การกำหนดสถานะยังเหมือนเดิม — dp[c] = มูลค่าสูงสุดที่ทำได้เมื่อมีความจุ c — แต่ทิศทางการวนจะเปลี่ยนไป เนื่องจากสามารถนำสิ่งของกลับมาใช้ซ้ำได้ เมื่ออัปเดต dp[c] เราจึงต้องเปิดโอกาสให้ใช้สิ่งของปัจจุบันซ้ำอีกครั้ง ดังนั้นจึงวนค่าความจุจากซ้ายไปขวา (ไปข้างหน้า)

การวนไปข้างหน้าทำให้ใช้ซ้ำได้

โปรดจำไว้ว่าในกระเป๋าเป้ 0/1 เราวนจากขวาไปซ้ายเพื่อป้องกันการใช้สิ่งของซ้ำ ส่วนในกระเป๋าเป้แบบไม่จำกัด เราทำตรงกันข้าม: วนจากซ้ายไปขวา เมื่อคำนวณ dp[c] ค่า dp[c-w] ได้รับการอัปเดตแล้วในการวนรอบปัจจุบัน ซึ่งหมายความว่าสิ่งของ i อาจถูกรวมไว้ก่อนแล้ว นี่คือสิ่งที่เราต้องการพอดี เพราะสามารถเพิ่มสิ่งของ i เข้าไปอีกครั้งในคำตอบที่มีสิ่งของ i อยู่แล้วได้

def unbounded_knapsack(weights, values, W):
    dp = [0] * (W + 1)
    
    for i in range(len(weights)):
        w, v = weights[i], values[i]
        for c in range(w, W + 1):  # iterate LEFT TO RIGHT
            dp[c] = max(dp[c], dp[c - w] + v)
    
    return dp[W]

weights = [1, 3, 4, 5]
values  = [1, 4, 5, 7]
print(unbounded_knapsack(weights, values, 7))  # 9

การทอนเงิน II: นับจำนวนวิธี

การทอนเงิน II ถามว่า เมื่อกำหนดชนิดของเหรียญและจำนวนเงินแล้ว มีวิธีที่แตกต่างกันกี่วิธีในการรวมเหรียญให้ได้จำนวนนั้น (เหรียญแต่ละชนิดใช้ได้ไม่จำกัดครั้ง) นี่เป็นรูปแบบหนึ่งของกระเป๋าเป้แบบไม่จำกัด ซึ่งแทนที่จะทำให้มูลค่าสูงสุด เราจะนับ combinations กำหนดให้ dp[c] เป็นจำนวนวิธีในการรวมเหรียญให้ได้จำนวนเงิน c กรณีฐานคือ dp[0] = 1 (มีหนึ่งวิธีในการได้ 0: ไม่เลือกอะไรเลย)

การใช้งานการทอนเงิน II

สำหรับเหรียญแต่ละชนิด ให้วนจำนวนเงินจากซ้ายไปขวาและสะสมค่า: dp[c] += dp[c - coin] กรณีฐาน dp[0] = 1 เป็นจุดเริ่มต้นของการนับ โปรดสังเกตว่าวงนอกวนตามเหรียญ และวงในวนตามจำนวนเงิน — ทำให้ได้จำนวน combinations โดยธรรมชาติ (ไม่ใช่ permutations) เพราะมูลค่าเหรียญแต่ละชนิดจะถูกพิจารณาเพียงครั้งเดียวในแต่ละรอบวงนอก

def change(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1  # one way to make amount 0
    
    for coin in coins:
        for c in range(coin, amount + 1):
            dp[c] += dp[c - coin]
    
    return dp[amount]

print(change(5, [1, 2, 5]))   # 4
print(change(3, [2]))          # 0
print(change(10, [10]))        # 1

combinations เทียบกับ permutations

ลำดับของวงวนมีความสำคัญอย่างยิ่ง หากให้จำนวนเงินอยู่ในวงนอกและเหรียญอยู่ในวงใน เราจะนับpermutations (ลำดับมีความสำคัญ) สำหรับ amount=5 และเหรียญ [1,2]: 1+2+2 และ 2+1+2 จะถูกนับแยกกัน หากให้เหรียญอยู่ในวงนอก เราจะนับcombinations (ลำดับไม่สำคัญ): 1+2+2 และ 2+1+2 ถือเป็นแบบเดียวกัน การทอนเงิน II ต้องการ combinations ดังนั้นเหรียญจึงอยู่ในวงนอก

# Count COMBINATIONS (order does not matter) — coin outer loop
def combinations(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for coin in coins:          # coin outer
        for c in range(coin, amount + 1):
            dp[c] += dp[c - coin]
    return dp[amount]

# Count PERMUTATIONS (order matters) — amount outer loop
def permutations(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for c in range(1, amount + 1):  # amount outer
        for coin in coins:
            if c >= coin:
                dp[c] += dp[c - coin]
    return dp[amount]

print(combinations(5, [1,2,5]))   # 4
print(permutations(5, [1,2,5]))   # 13

ปัญหาการตัดแท่ง

อีกปัญหาคลาสสิกของกระเป๋าเป้แบบไม่จำกัด: กำหนดแท่งความยาว n และราคาสำหรับแท่งแต่ละความยาวตั้งแต่ 1 ถึง n ให้หารายได้สูงสุดด้วยการตัดแท่งอย่างเหมาะสม ชิ้นส่วนแต่ละชิ้นที่มีความยาว l สามารถขายได้ในราคา price[l] และสามารถใช้ชิ้นส่วนซ้ำได้ (แท่งสามารถถูกตัดเป็นชิ้นส่วนหลายชิ้นที่มีความยาวเท่ากัน) ปัญหานี้ตรงกับกระเป๋าเป้แบบไม่จำกัด โดยมี W = n และสิ่งของคือความยาวของชิ้นตัดแต่ละแบบ

def rod_cutting(prices, n):
    # prices[i] = price of rod of length i+1
    dp = [0] * (n + 1)
    
    for length in range(1, n + 1):   # each cut length
        price = prices[length - 1]
        for c in range(length, n + 1):
            dp[c] = max(dp[c], dp[c - length] + price)
    
    return dp[n]

prices = [1, 5, 8, 9, 10, 17, 17, 20]
print(rod_cutting(prices, 8))  # 22

การทอนเงิน I: จำนวนเหรียญต่ำสุด

การทอนเงิน I (เป็นคนละปัญหากัน) ต้องการหาจำนวนเหรียญที่น้อยที่สุดเพื่อให้ได้จำนวนเงินเป้าหมาย ในกรณีนี้ dp[c] = จำนวนเหรียญต่ำสุดที่ทำให้ได้จำนวนเงิน c สมการเวียนเกิดคือ dp[c] = min(dp[c], dp[c - coin] + 1) กำหนดค่าเริ่มต้นของทุกรายการเป็น inf ยกเว้น dp[0] = 0 ปัญหานี้เป็นแบบไม่จำกัดเช่นกัน (สามารถใช้เหรียญซ้ำได้) จึงต้องวนจากซ้ายไปขวา ให้คืนค่า dp[amount] หากเป็นค่าจำกัด มิฉะนั้นให้คืนค่า -1

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    
    for coin in coins:
        for c in range(coin, amount + 1):
            dp[c] = min(dp[c], dp[c - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1

print(coinChange([1,5,6,9], 11))  # 2 (5+6 or other combos)
print(coinChange([2], 3))          # -1

ความแตกต่างสำคัญ: ค่าสูงสุด เทียบกับค่าต่ำสุด เทียบกับการนับจำนวน

กระเป๋าเป้แบบไม่จำกัดทั้งสามรูปแบบใช้การดำเนินการต่างกันกับ dp[c-coin]: ทำให้มูลค่าสูงสุด: dp[c] = max(dp[c], dp[c-w] + v); กำหนดค่าเริ่มต้นเป็น 0 ทำให้ต้นทุนต่ำสุด: dp[c] = min(dp[c], dp[c-coin] + 1); กำหนดค่าเริ่มต้นเป็น inf, dp[0]=0 นับจำนวนวิธี: dp[c] += dp[c-coin]; กำหนดค่าเริ่มต้นเป็น 0, dp[0]=1 การระบุให้ได้ว่าควรใช้รูปแบบใดถือเป็นครึ่งหนึ่งของการแก้โจทย์สัมภาษณ์

ความซับซ้อนและเคล็ดลับการสัมภาษณ์

กระเป๋าเป้แบบไม่จำกัดทุกรูปแบบทำงานในเวลา O(n × W) และใช้หน่วยความจำ O(W) โดย n คือจำนวนประเภทสิ่งของ และ W คือจำนวนเงินเป้าหมาย สำหรับปัญหาเหรียญ n คือจำนวนชนิดของเหรียญ ในการสัมภาษณ์ ให้ระบุรูปแบบให้ชัดเจน (ค่าสูงสุด/ค่าต่ำสุด/การนับจำนวน) เขียน DP 1 มิติ และบอกให้ชัดว่าวงนอกวนตามเหรียญหรือตามจำนวนเงิน — ผู้สัมภาษณ์ทราบว่าความแตกต่างนี้ใช้ทดสอบความเข้าใจ DP อย่างลึกซึ้ง

การแยกแยะกระเป๋าเป้แบบไม่จำกัดกับแบบ 0/1

ใช้สัญญาณต่อไปนี้เพื่อระบุว่าควรใช้รูปแบบใด: ใช้ซ้ำได้ไม่จำกัด → แบบไม่จำกัด (วนไปข้างหน้า); สิ่งของแต่ละชิ้นใช้ได้เพียงครั้งเดียว → แบบ 0/1 (วนย้อนกลับ); โจทย์ระบุว่า 'กี่ครั้งก็ได้', 'มีสิ่งของไม่จำกัด', หรือ 'อนุญาตให้ใช้ซ้ำ' → แบบไม่จำกัด ตัวอย่างเช่น การทอนเงิน การตัดแท่ง และการแยกจำนวนเต็ม ล้วนเป็นแบบไม่จำกัด ส่วนผลรวมเซตย่อย การแบ่งเซต และกระเป๋าเป้ 0/1 เป็นแบบ 0/1 การจำแนกผิดจะทำให้ได้คำตอบผิดซึ่งแก้ไขข้อผิดพลาดได้ยาก

การแยกจำนวนเต็มและรูปแบบอื่น ๆ

การแยกจำนวนเต็ม (LeetCode 343): แบ่งจำนวนเต็ม n ออกเป็นจำนวนเต็มบวกอย่างน้อย 2 จำนวน เพื่อทำให้ผลคูณสูงสุด ปัญหานี้เป็นกระเป๋าเป้แบบไม่จำกัด โดย 'สิ่งของ' คือจำนวนเต็มตั้งแต่ 2 ถึง n-1 กำหนดให้ dp[i] = ผลคูณสูงสุดของจำนวนเต็มที่รวมกันได้ i สำหรับสิ่งของแต่ละชิ้น j ตั้งแต่ 2 ถึง i ให้ใช้ dp[i] = max(dp[i], max(j, dp[j]) * max(i-j, dp[i-j])) ซึ่งแสดงให้เห็นว่ารูปแบบกระเป๋าเป้แบบไม่จำกัดสามารถนำไปใช้ได้กว้างกว่าบริบทของเหรียญ

def integerBreak(n):
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        for j in range(1, i):
            dp[i] = max(dp[i], max(j, dp[j]) * max(i-j, dp[i-j]))
    return dp[n]

print(integerBreak(10))  # 36 (3+3+4 = 3*3*4 = 36)

ตรวจสอบความเข้าใจ

ทดสอบความเข้าใจแนวคิดโครงสร้างข้อมูลและอัลกอริทึม — การเตรียมตัวสัมภาษณ์การเขียนโปรแกรมจากบทเรียนนี้

ทบทวนบทเรียน

ในบทเรียนนี้ คุณได้เรียนรู้ว่า: กระเป๋าเป้แบบไม่จำกัดจะวนค่าความจุจากซ้ายไปขวาเพื่อให้ใช้สิ่งของซ้ำได้, การทอนเงิน II จะนับ combinations โดยให้เหรียญอยู่ในวงนอก, และ ทั้งสามรูปแบบ — ทำให้ค่าสูงสุด ทำให้ค่าต่ำสุด และนับจำนวน — แตกต่างกันเพียงการดำเนินการกับ DP และการกำหนดค่าเริ่มต้น บทถัดไป เราจะใช้กระเป๋าเป้ 0/1 เพื่อแก้ปัญหาการแบ่งเซตย่อยให้ผลรวมเท่ากัน

คำถามที่พบบ่อย

บทเรียน “กระเป๋าเป้ไม่จำกัดจำนวนและการทอนเหรียญ II” ฟรีหรือไม่

ใช่ — ข้อความเต็มของ “กระเป๋าเป้ไม่จำกัดจำนวนและการทอนเหรียญ II” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Coding Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน

คุณจะเรียนรู้อะไรในบทเรียน “กระเป๋าเป้ไม่จำกัดจำนวนและการทอนเหรียญ II”

อนุญาตให้นำสิ่งของกลับมาใช้ซ้ำด้วยการวนความจุจากน้อยไปมาก แล้วแก้ปัญหาการทอนเหรียญ II (นับจำนวนวิธี) และการตัดแท่งด้วยรูปแบบนี้ คุณปฏิบัติ Coding Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน

คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Coding Interview Prep หรือไม่

ไม่จำเป็นต้องมีประสบการณ์มาก่อน Coding Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน

บทเรียน “กระเป๋าเป้ไม่จำกัดจำนวนและการทอนเหรียญ II” ใช้เวลานานแค่ไหน

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

ฉันเขียนและรันโค้ดในบทเรียน Coding Interview Prep นี้ได้ไหม

ได้ บทเรียน Coding Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ

บทเรียนทั้งหมดในหลักสูตรนี้

  1. กระเป๋าเป้ 0/1 และการลดการใช้หน่วยความจำ
  2. กระเป๋าเป้ไม่จำกัดจำนวนและการทอนเหรียญ II
  3. ผลรวมเซตย่อยเท่ากันของการแบ่งพาร์ทิชัน
  4. ผลรวมเป้าหมายพร้อมเครื่องหมายบวกและลบ
← กลับไปที่ Coding Interview Prep