تخيل إنك مسافر ومعاك شنطة سعتها محدودة:
كل حاجة إما تاخدها كلها أو تسيبها
→ لازم DP
ممكن تاخد جزء من أي حاجة
→ Greedy بينفع!
Laptop
الوزن: 3kg
القيمة: $4000
Guitar
الوزن: 1kg
القيمة: $1500
Speaker
الوزن: 4kg
القيمة: $3000
Camera
الوزن: 2kg
القيمة: $2500
0/1 Knapsack - بناء جدول الحلول
نبني جدول: كل صف = حاجة، كل عمود = سعة (من 0 للـ max)
dp[i][w] = أعلى قيمة ممكنة باستخدام أول i حاجات وسعة w
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|---|
| ∅ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 💻3kg | 0 | 0 | 0 | 4K | 4K | 4K | 4K | 4K |
| 🎸1kg | 0 | 1.5K | 1.5K | 4K | 5.5K | 5.5K | 5.5K | 5.5K |
| 🔊4kg | 0 | 1.5K | 1.5K | 4K | 5.5K | 5.5K | 5.5K | 7K |
| 📸2kg | 0 | 1.5K | 2.5K | 4K | 5.5K | 6.5K | 8K | 8K |
✓ الإجابة: $8,000
اخد: 💻 Laptop (3kg, $4K) + 🎸 Guitar (1kg, $1.5K) + 📸 Camera (2kg, $2.5K) = 6kg
dp[i][w] =
if weight[i] > w: dp[i-1][w] // مش هينفع ناخدها
else: max( dp[i-1][w], value[i] + dp[i-1][w-weight[i]] )
function knapsack(weights, values, capacity) {
const n = weights.length;
const dp = Array(n + 1).fill(null)
.map(() => Array(capacity + 1).fill(0));
for (let i = 1; i <= n; i++) {
for (let w = 1; w <= capacity; w++) {
// Don't take item i
dp[i][w] = dp[i - 1][w];
// Take item i (if possible)
if (weights[i - 1] <= w) {
const take = values[i - 1] +
dp[i - 1][w - weights[i - 1]];
dp[i][w] = Math.max(dp[i][w], take);
}
}
}
return dp[n][capacity];
}n: عدد الحاجات
W: السعة الكلية
للجدول 2D
ممكن يتحسن لـ O(W) بس!