ملاحظة قراءة الخوارزمية

Knapsack Problem

In 0/1 knapsack, each item has a weight and value and may be chosen at most once. The goal is maximum total value without exceeding capacity.

النوعخوارزميةالفئةSets & Dynamic Programmingالعمقمتقدمالتعقيد المعتادO(nW) DP

إجابة مقابلة قصيرة

ابدأ بهذا النموذج الذهني

In 0/1 knapsack, each item has a weight and value and may be chosen at most once. The goal is maximum total value without exceeding capacity.

شرح مبسط

كيف يعمل، بلا مصطلحات زائدة

A DP state can represent the best value using the first i items with capacity c.

For each item, either skip it or take it if it fits.

التنفيذ

اقرأ الخوارزمية كسلسلة من القرارات

Define the state precisely.

Write the transition/choice from smaller states.

Set base cases, then decide memoization, tabulation or backtracking.

مثال صغير لتحتفظ به في ذهنك

Read a tiny input by hand and write down the state after every important operation. For Knapsack Problem, the goal is to make the invariant visible rather than to memorize code.

تطبيق JavaScript قابل للقراءةJavaScript

function knapsack(items, capacity) {
  const dp = Array(capacity + 1).fill(0);
  for (const { weight, value } of items) {
    for (let c = capacity; c >= weight; c--) {
      dp[c] = Math.max(dp[c], dp[c - weight] + value);
    }
  }
  return dp[capacity];
}

كيف تقرأ هذا الكود

لا تحفظ الصياغة. تتبع الحالة التي تتغير في كل سطر واربطها بالثابت الموضح أعلاه.

التعقيد

O(nW) DP

Do not quote this complexity mechanically. Ask which operation or input dimension it describes, then derive the cost from the loops, recursion depth, data-structure operations and any preprocessing assumptions.

متى تستخدمه

مناسب لـ

Use DP when subproblems overlap and optimal solutions can be composed from smaller optimal states.

أخطاء شائعة

ما الذي يسوء عادةً

Writing recurrence before defining state.
Using DP when state space is larger than the original problem.

كيف تشرحه في المقابلة

صيغة إجابة احترافية

Clarify the variant first—0/1, unbounded or fractional. Their correct algorithms differ substantially.

المشكلة→الفكرة الأساسية→الثابت / الحالة→Big-O→المفاضلة

فحص سريع للمقابلة

What problem does Knapsack Problem solve?

In 0/1 knapsack, each item has a weight and value and may be chosen at most once. The goal is maximum total value without exceeding capacity.

ماذا يجب أن أذكر عن التعقيد؟

Its typical cost here is O(nW) DP, but a complete answer should connect that cost to the representation, input constraints and the dominant operations.

ما الخطأ الأكثر شيوعاً؟

Writing recurrence before defining state.

متابعة القراءةMemoizationTabulationBacktracking

function knapsack(items, capacity) { const dp = Array(capacity + 1).fill(0); for (const { weight, value } of items) { for (let c = capacity; c >= weight; c--) { dp[c] = Math.max(dp[c], dp[c - weight] + value); } } return dp[capacity]; }