หาจำนวนเงินขั้นต่ำและสูงสุดในการซื้อขนม N ชนิดใน Python

สมมติว่ามีขนม N ชนิด ราคาแต่ละชนิดกำหนดไว้ ร้านมีโปรโมชั่น ซื้อ 1 ชิ้น รับฟรีได้สูงสุด K ชนิดที่ต่างกัน หาจำนวนเงินขั้นต่ำและสูงสุดที่ต้องจ่ายเพื่อซื้อขนมครบทุก N ชนิด โดยต้องใช้โปรโมชั่นให้ได้มากที่สุด

เช่น price = [4, 3, 2, 5], k = 2 ผลลัพธ์ Minimum = 5, Maximum = 9

• ขั้นต่ำ: ซื้อราคา 2 รับฟรี 4, 5 แล้วซื้อ 3 รวม 5
• สูงสุด: ซื้อราคา 5 รับฟรี 2, 3 แล้วซื้อ 4 รวม 9

ขั้นตอนการแก้ปัญหา

1. ฟังก์ชัน get_min(A, k): เรียงราคาน้อยไปมาก ซื้อราคาถูกก่อน รับฟรีราคาแพง
2. ฟังก์ชัน get_max(A, k): เรียงราคาน้อยไปมาก ซื้อราคาแพงก่อน รับฟรีราคาถูก

ตัวอย่างโค้ด Python

def get_min(A, k):
    n = len(A)
    A.sort()
    res = 0
    i = 0
    while n:
        res += A[i]
        n -= k
        i += 1
    return res

def get_max(A, k):
    n = len(A)
    A.sort()
    res = 0
    idx = 0
    i = n - 1
    while i >= idx:
        res += A[i]
        idx += k
        i -= 1
    return res

A = [4, 3, 2, 5]
k = 2
print(get_min(A, k), get_max(A, k))

อินพุต

[4, 3, 2, 5], 2

เอาต์พุต

5 9