สมมติว่าเรามีรายการความยาวเท่ากันสองรายการซึ่งเรียกว่าน้ำหนักและค่า และเรายังมีความจุอีกค่าหนึ่ง โดยที่ weights[i] และ values[i] แสดงถึงน้ำหนักและมูลค่าของไอเท็ม ith หากเรารับน้ำหนักได้สูงสุด และเราสามารถถ่ายสำเนาได้กี่ชุดสำหรับแต่ละรายการ เราต้องหามูลค่าสูงสุดที่เราจะได้รับ
ดังนั้น หากอินพุตเป็นเหมือนน้ำหนัก =[1, 2, 3] ค่า =[1, 5, 3] ความจุ =5 ผลลัพธ์จะเป็น 11
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดฟังก์ชัน dp() นี่จะใช้เวลา i, k
- ถ้าฉันเท่ากับขนาดของน้ำหนัก แล้ว
- คืน 0
- ตอบ :=dp(i + 1, k)
- ถ้า k>=weights[i] แล้ว
- ans :=สูงสุดของ ans และ dp(i, k - weights[i]) + ค่า[i]
- คืนสินค้า
- จากวิธีหลัก ให้ทำดังนี้ -
- ผลตอบแทน dp(0, ความจุ)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class Solution: def solve(self, weights, values, capacity): def dp(i, k): if i == len(weights): return 0 ans = dp(i + 1, k) if k >= weights[i]: ans = max(ans, dp(i, k - weights[i]) + values[i]) return ans return dp(0, capacity) ob = Solution() weights = [1, 2, 3] values = [1, 5, 3] capacity = 5 print(ob.solve(weights, values, capacity))
อินพุต
[1, 2, 3], [1,5,3], 5
ผลลัพธ์
11
