โปรแกรมหาค่าสูงสุดในปัญหากระเป๋าแบบทีบได้หลายชิ้นใน Python

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

ตัวอย่าง: weights = [1, 2, 3], values = [1, 5, 3], capacity = 5 ผลลัพธ์คือ 11

ขั้นตอนการแก้ปัญหา (Dynamic Programming แบบ Memoization)

1. กำหนดฟังก์ชัน dp(i, k):
   • ถ้า i == len(weights) คืนค่า 0
   • ans = dp(i + 1, k) (ไม่เอาไอเทม i)
   • ถ้า k >= weights[i]:
     • ans = max(ans, dp(i, k - weights[i]) + values[i]) (เอาไอเทม i ซ้ำได้)
   • คืนค่า ans
2. จากเมธอดหลัก เรียก dp(0, capacity)

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

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))  # Output: 11

อินพุต / เอาต์พุต

Input: [1, 2, 3], [1,5,3], 5

Output: 11