ปัญหา 0/1 Knapsack: ให้ weights, values ความยาวเท่ากัน และความจุ capacity เลือกสิ่งของแต่ชิ้นได้สูงสุด 1 ชิ้น หาค่ารวมสูงสุด
ตัวอย่าง: weights=[2,3,4], values=[2,6,4], capacity=6 → 8 (เลือกชิ้นที่ 1 และ 2)
Dynamic Programming
dp[i][j]: ค่าสูงสุดใช้สิ่งของ i ชิ้นแรก ความจุ j- Transition: ไม่เลือก → dp[i-1][j], เลือก (ถ้าน้ำหนักพอ) → dp[i-1][j-w]+v
การนำไปใช้
class Solution:
def solve(self, weights, values, capacity):
n = len(weights)
dp = [[0]*(capacity+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, capacity+1):
if weights[i-1] <= j:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1])
else:
dp[i][j] = dp[i-1][j]
return dp[n][capacity]
ob = Solution()
print(ob.solve([2,3,4], [2,6,4], 6)) # 8
