สมมติว่าเรามีรายการตัวเลขสองรายการ อันหนึ่งเรียกว่าตุ้มน้ำหนัก อีกอันเรียกว่าค่านิยม เหล่านี้มีความยาวเท่ากัน เรายังมีค่าสองค่าที่เรียกว่าความจุและการนับ โดยที่ weights[i] และ values[i] แสดงถึงน้ำหนักและมูลค่าของไอเท็ม ith เราสามารถเก็บน้ำหนักได้สูงสุดและนับรวมได้มากที่สุด และเราสามารถรับได้เพียงสำเนาเดียวของแต่ละรายการ ดังนั้นเราต้องหาจำนวนมูลค่าสูงสุดที่เราจะได้รับ
ดังนั้นหากอินพุตเป็นเหมือนน้ำหนัก =[2, 2, 4, 6] ค่า =[15, 15, 20, 35] ความจุ =8 จำนวน =3 ผลลัพธ์จะเป็น 50 ตามที่เราเลือกได้ 3 รายการแรก เนื่องจากน้ำหนักรวมเท่ากับ 8
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
รายการ :=รายการคู่โดยนำน้ำหนักและค่า
-
กำหนดฟังก์ชัน dp() นี่จะใช้เวลา i, cp, ct
-
ถ้าฉันเท่ากับขนาดของสิ่งของหรือ ct เท่ากับ 0 แล้ว
-
ผลตอบแทน 0.0
-
-
(w, v) :=รายการ[i]
-
ตอบ :=dp(i + 1, cp, ct)
-
ถ้า cp> =w แล้ว
-
ans :=สูงสุดของ ans, dp(i + 1, cp - w, ct - 1) + v
-
-
กลับมาอีกครั้ง
-
จากวิธีหลักส่งคืน dp(0, ความจุ, นับ)
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
class Solution: def solve(self, weights, values, capacity, count): items = list(zip(weights, values)) def dp(i, cp, ct): if i == len(items) or ct == 0: return 0.0 w, v = items[i] ans = dp(i + 1, cp, ct) if cp >= w: ans = max(ans, dp(i + 1, cp - w, ct - 1) + v) return ans return int(dp(0, capacity, count)) ob = Solution() weights = [2, 2, 4, 6] values = [15, 15, 20, 35] capacity = 8 count = 3 print(ob.solve(weights, values, capacity, count))
อินพุต
[2, 2, 4, 6], [15, 15, 20, 35], 8, 3
ผลลัพธ์
50
