โปรแกรมหาจำนวนเงินสูงสุดที่เราสามารถรับได้โดยการนำสิ่งของต่าง ๆ ภายในความจุใน Python

สมมติว่าเรามีรายการสองรายการที่เรียกว่าน้ำหนักและค่าซึ่งมีความยาวเท่ากันและอีกจำนวนหนึ่งเรียกว่าความจุ k ที่นี่ weights[i] และ values[i] จะแสดงน้ำหนักและมูลค่าของรายการ ith ตอนนี้ เราสามารถรับน้ำหนักได้มากสุด k ความจุ และเราสามารถถ่ายได้มากสุดหนึ่งสำเนาของแต่ละรายการ เราต้องค้นหาจำนวนมูลค่าสูงสุดที่เราจะได้รับ

ดังนั้น หากอินพุตเป็นเหมือนน้ำหนัก =[2, 3, 4], ค่า =[2, 6, 4], ความจุ =6 ผลลัพธ์จะเป็น 8

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

• n:=ขนาดของน้ำหนัก
• dp:=เมทริกซ์ขนาดความจุ x n และเติมด้วย 0
• สำหรับ i ในช่วง 0 ถึง n ให้ทำ
  • สำหรับ j ในช่วง 0 ถึงความจุ ทำ
    • ถ้าฉันเหมือนกับ 0 หรือ j เหมือนกับ 0 แล้ว
      • dp[i, j]:=0
    • มิฉะนั้น เมื่อ weights[i-1] <=j แล้ว
      • dp[i,j] =สูงสุดของ (dp[i-1, j-weights[i - 1]] + ค่า[i-1]) และ (dp[i-1, j])
    • มิฉะนั้น
      • dp[i, j]:=dp[i-1, j]
• ผลตอบแทน dp[n, ความจุ]

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

ตัวอย่าง

class Solution:
   def solve(self, weights, values, capacity):
      n=len(weights)
      dp=[[0 for i in range(capacity+1)]
      for _ in range(n+1)]
         for i in range(n+1):
            for j in range(capacity+1):
               if i==0 or j==0:
                  dp[i][j]=0
                  elif weights[i-1]<=j:
                     dp[i][j]=max(dp[i-1][j-weights[i-1]]+values[i-1],dp[i-1][j])
                  else:
                     dp[i][j]=dp[i-1][j]
      return dp[n][capacity]
ob = Solution() weights = [2, 3, 4] values = [2, 6, 4]
capacity = 6
print(ob.solve(weights, values, capacity))

อินพุต

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

ผลลัพธ์

8