ได้รับ weights, values ความยาวเท่ากัน และ capacity, count สามารถเลือกของได้สูงสุด count ชิ้น น้ำหนักรวม ≤ capacity แต่ละชิ้นเลือกได้สูงสุด 1 ครั้ง หา value สูงสุด
ตัวอย่าง
weights = [2, 2, 4, 6], values = [15, 15, 20, 35]
capacity = 8, count = 3 → Output: 50 (เลือก 3 ชิ้นแรก น้ำหนัก 2+2+4=8, value 15+15+20=50)
แนวทางแก้ปัญหา
เป็น 0/1 Knapsack พร้อมข้อจำกัดจำนวนชิ้น ใช้ Memoized Recursion (Top-down DP):
- State:
dp(i, cap_left, cnt_left)= value สูงสุดจาก item i เป็นต้นไป - Base:
i == nหรือcnt_left == 0→ 0 - Transition: ไม่เลือก item i, หรือ เลือก (ถ้าน้ำหนักพอ)
การใช้งาน (Python)
from functools import lru_cache
class Solution:
def solve(self, weights, values, capacity, count):
items = list(zip(weights, values))
n = len(items)
@lru_cache(None)
def dp(i, cap, cnt):
if i == n or cnt == 0:
return 0
w, v = items[i]
# ไม่เลือก
ans = dp(i + 1, cap, cnt)
# เลือก
if cap >= w:
ans = max(ans, dp(i + 1, cap - w, cnt - 1) + v)
return ans
return dp(0, capacity, count)
# ทดสอบ
ob = Solution()
weights = [2, 2, 4, 6]
values = [15, 15, 20, 35]
print(ob.solve(weights, values, 8, 3)) # Output: 50
ความซับซ้อน
- Time Complexity: O(N × capacity × count)
- Space Complexity: O(N × capacity × count)
สำหรับค่าใหญ่ควรใช้ Bottom-up DP หรือปรับปรุงพื้นที่หน่วยความจำ
