โปรแกรมหาหน่วยสูงสุดที่สามารถวางบนรถบรรทุกใน Python

สมมติว่าเรามีชุดกล่องที่แสดงเป็นอาร์เรย์ 2 มิติที่เรียกว่า boxTypes โดยที่ boxTypes[i] ประกอบด้วยสององค์ประกอบ [จำนวนกล่องประเภท i จำนวนหน่วยต่อกล่องประเภท i] ตอนนี้ เรายังมีค่า k อีกค่าหนึ่ง ซึ่งเป็นจำนวนกล่องสูงสุดที่บรรทุกบนรถบรรทุกคันนั้นได้ เราสามารถเลือกกล่องใดก็ได้ที่จะวางบนรถบรรทุกตราบเท่าที่จำนวนกล่องไม่ผ่าน k เราต้องหาจำนวนยูนิตสูงสุดที่จะวางบนรถบรรทุกได้

ดังนั้นหากอินพุตเป็นเหมือน boxTypes =[[2,4],[3,3],[4,2]], k =6 ผลลัพธ์จะเป็น 19 เพราะมี

• แบบที่ 1 จำนวน 2 กล่อง กล่องละ 4 ยูนิต

• แบบที่ 2 จำนวน 3 กล่อง กล่องละ 3 ยูนิต

• แบบที่ 3 จำนวน 4 กล่อง กล่องละ 2 ยูนิต

เมื่อ k =6 เราเอากล่องประเภทที่ 1 และ 2 มาทั้งหมด และประเภทที่ 3 จะมีเพียงกล่องเดียว ดังนั้นจะมี (2*4) + (3*3) + 2 =8 + 9 +2 =19 รายการ .

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• sort boxTypes ตามจำนวนรายการที่ปรากฏในแต่ละช่อง

• รวม :=0, เติม :=0

• สำหรับแต่ละ i ใน boxTypes ทำ

  • ถ้าเติม + i[0] <=k แล้ว

    • เติม :=เติม + ผม[0]

    • ทั้งหมด :=ทั้งหมด + i[0] * i[1]

  • มิฉะนั้น

    • รวม :=รวม + (k - เติม) * i[1]

    • ออกจากวง

• ผลตอบแทนรวม

ตัวอย่าง (Python)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

def solve(boxTypes, k):
   boxTypes.sort(key = lambda x : x[1], reverse = True)
   total = 0
   fill = 0
   for i in boxTypes:
      if fill + i[0] <= k:
         fill += i[0]
         total += i[0] * i[1]
      else:
         total += (k - fill) * i[1]
         break
   return total

boxTypes = [[2,4],[3,3],[4,2]]
k = 6
print(solve(boxTypes, k))

อินพุต

[[2,4],[3,3],[4,2]], 6

ผลลัพธ์

19