ตรวจสอบว่าสามารถได้อัตราส่วนจากช่วงต้นทุนและปริมาณที่กำหนด (Python)

โจทย์: กำหนดช่วงต้นทุน [lowCost, upCost] และช่วงปริมาณ [lowQuant, upQuant] หาว่ามีคู่ (cost, quantity) ที่ cost/quantity = r อยู่ในช่วงหรือไม่

ตัวอย่าง: lowCost=2, upCost=10, lowQuant=3, upQuant=9, r=3 → quantity=3 → cost=9 ∈ [2,10] → True

อัลกอริทึม

วนลูป quantity จาก lowQuant ถึง upQuant คำนวณ cost = quantity × r ถ้า cost ∈ [lowCost, upCost] → True

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

def can_we_find_r(l_cost, u_cost, l_quant, u_quant, ratio):
    for q in range(l_quant, u_quant + 1):
        cost = q * ratio
        if l_cost <= cost <= u_cost:
            return True
    return False

print(can_we_find_r(2, 10, 3, 9, 3))  # True

ผลลัพธ์

True

สรุป: Brute force O(upQuant - lowQuant) เพราะ quantity เป็นจำนวนเต็ม สำหรับช่วงใหญ่ ควรใช้คณิตศาสตร์: ตรวจสอบช่วง [lowCost, upCost] และ [lowQuant×r, upQuant×r] ทับซ้อนกันหรือไม่