{"id":53,"date":"2026-02-25T23:25:15","date_gmt":"2026-02-25T15:25:15","guid":{"rendered":"https:\/\/blog.mirpri.com\/?p=53"},"modified":"2026-02-25T23:56:25","modified_gmt":"2026-02-25T15:56:25","slug":"the-knapsack-problem","status":"publish","type":"post","link":"https:\/\/blog.mirpri.com\/index.php\/the-knapsack-problem\/","title":{"rendered":"The Knapsack Problem: From 0\/1 to Advanced"},"content":{"rendered":"\n

The Knapsack problem is the “Hello World” of Dynamic Programming. But beyond the basic 0\/1 version lies a world of clever optimizations and mathematical tricks. In this post, we\u2019ll break down the three major types and the patterns that solve them.<\/p>\n\n\n\n

\n\n\n\n

1. The Foundation: 0\/1 Knapsack<\/h2>\n\n\n\n

The Rule:<\/strong> You have one of each item. You either take it (1) or leave it (0).<\/p>\n\n\n\n

The Logic<\/h3>\n\n\n\n

We define dp[i][j]<\/code> as the maximum value using a subset of the first i<\/code> items with a total capacity j<\/code>.<\/p>\n\n\n\n

The choice is simple:<\/p>\n\n\n\n

    \n
  1. Exclude<\/strong> the current item: dp[i-1][j]<\/code><\/li>\n\n\n\n
  2. Include<\/strong> the current item: dp[i-1][j - w_i] + v_i<\/code><\/li>\n<\/ol>\n\n\n\n

    The “Space” Pro-Tip<\/h3>\n\n\n\n

    You don’t need a 2D array. By iterating backwards<\/strong> through the capacity, you can use a single 1D array.<\/p>\n\n\n\n

    Just update backward to avoid using the same item twice.<\/p>\n\n\n\n

    for item in items:\n    for j in range(W, item.w - 1, -1):\n        dp[j] = max(dp[j], dp[j - item.w] + item.v)\n<\/code><\/pre>\n\n\n\n
    \n\n\n\n
    2. The Buffet: Complete Knapsack<\/h2>\n\n\n\n
    The Rule:<\/strong> Items are infinite. Take as many as you want.<\/p>\n\n\n\n
    The Transformation<\/h3>\n\n\n\n
    If you can take an item multiple times, the state $dp[j]$ should depend on the current<\/strong> item’s updated state, not the previous one.<\/p>\n\n\n\n
    The Simple Twist<\/h3>\n\n\n\n
    The code is almost identical to 0\/1 Knapsack, but we iterate forwards<\/strong>.<\/p>\n\n\n\n
    for item in items:\n    for j in range(item.w, W + 1):\n        dp[j] = max(dp[j], dp[j - item.w] + item.v)\n<\/code><\/pre>\n\n\n\n
    \n\n\n\n
    3. The Constraint: Bounded Knapsack<\/h2>\n\n\n\n
    The Rule:<\/strong> Each item i<\/mi>i<\/annotation><\/semantics><\/math> has a specific limit n<\/mi>i<\/mi><\/msub>n_i<\/annotation><\/semantics><\/math>.<\/p>\n\n\n\n
    Approach A: Binary Splitting (The Clever Way)<\/h3>\n\n\n\n
    A straightforward approach is to treat each item as n<\/mi>i<\/mi><\/msub>n_i<\/annotation><\/semantics><\/math> different items, each item has the same price and value. But it significantly slows down the algorithm.<\/p>\n\n\n\n
    So instead of treating it as n<\/mi>i<\/mi><\/msub>n_i<\/annotation><\/semantics><\/math> individual items, we split n<\/mi>i<\/mi><\/msub>n_i<\/annotation><\/semantics><\/math> into powers of 2.<\/p>\n\n\n\n
    For example, if you have 13 items, split them into packs of 1, 2, 4, and 6<\/em><\/strong>. (Note that they should add up to n<\/mi>i<\/mi><\/msub>n_i<\/annotation><\/semantics><\/math>.) These four “new” items can combine to form any number from 1 to 13.<\/p>\n\n\n\n
      \n
    • Complexity:<\/strong> O<\/mi>(<\/mo>W<\/mi>\u22c5<\/mo>\u2211<\/mo>log<\/mi>\u2061<\/mo><\/mspace><\/mrow>n<\/mi>i<\/mi><\/msub>)<\/mo><\/mrow>O(W \\cdot \\sum \\log n_i)<\/annotation><\/semantics><\/math><\/li>\n<\/ul>\n\n\n\n
      Approach B: Monotonic Queue (The Ultimate Way)<\/h3>\n\n\n\n
      For tight time limits, we use a Monotonic Queue<\/strong>. We group capacities by j<\/mi><\/mo><\/mspace>(<\/mo><\/mtext>mod<\/mi><\/mrow><\/mspace>w<\/mi>i<\/mi><\/msub>)<\/mo><\/mrow>j \\pmod{w_i}<\/annotation><\/semantics><\/math>. For each group, we find the maximum value in a “sliding window” of size n<\/mi>i<\/mi><\/msub>n_i<\/annotation><\/semantics><\/math>.<\/p>\n\n\n\n
        \n
      • Complexity:<\/strong> O<\/mi>(<\/mo>N<\/mi>\u22c5<\/mo>W<\/mi>)<\/mo><\/mrow>O(N \\cdot W)<\/annotation><\/semantics><\/math> \u2014 the gold standard.<\/li>\n<\/ul>\n\n\n\n
        Detailed implementation<\/summary>\n
        1. The Core Observation<\/h3>\n\n\n\n
        For an item with weight $w$, value $v$, and count $n$, notice that a capacity $j$ can only be updated by capacities like $j-w, j-2w, \\dots, j-kw$ (where $k \\le n$).<\/p>\n\n\n\n
        This means the capacities are partitioned into disjoint sets<\/strong> based on their remainder when divided by $w$.<\/p>\n\n\n\n
          \n
        • Set 0:<\/strong> $0, w, 2w, 3w, \\dots$<\/li>\n\n\n\n
        • Set 1:<\/strong> $1, w+1, 2w+1, 3w+1, \\dots$<\/li>\n\n\n\n
        • Set $r$:<\/strong> $r, w+r, 2w+r, \\dots$<\/li>\n<\/ul>\n\n\n\n
          The algorithm processes each remainder $r \\in [0, w-1]$ independently.<\/p>\n\n\n\n
          \n\n\n\n
          2. The Sliding Window Transformation<\/h3>\n\n\n\n
          Let\u2019s look at the transition for a specific remainder $r$. Let $j = k \\cdot w + r$. The state looks like this:<\/p>\n\n\n\n
          $$dp[k \\cdot w + r] = \\max_{k-n \\le i \\le k-1} \\{ dp[i \\cdot w + r] + (k – i) \\cdot v \\}$$<\/p>\n\n\n\n
          To make this look like a standard “sliding window maximum” problem, we rearrange the terms:<\/p>\n\n\n\n
          $$dp[k \\cdot w + r] = \\max_{k-n \\le i \\le k-1} \\{ dp[i \\cdot w + r] – i \\cdot v \\} + k \\cdot v$$<\/p>\n\n\n\n
          Now, as $k$ increases, we are looking for the maximum value of $(dp[i \\cdot w + r] – i \\cdot v)$ in a window of size $n$.<\/p>\n\n\n\n
          \n\n\n\n
          3. Using the Monotonic Queue<\/h3>\n\n\n\n
          A monotonic queue is a deque (double-ended queue) that keeps elements in decreasing order<\/strong>.<\/p>\n\n\n\n
            \n
          1. Maintain the Window:<\/strong> As we move to the next $k$, we remove indices from the front of the queue that are “out of date” (older than $k-n$).<\/li>\n\n\n\n
          2. Maintain Monotonicity:<\/strong> Before adding the new value $(dp[k \\cdot w + r] – k \\cdot v)$ to the back, we remove all values smaller than it. Why? Because a newer, larger value is always a better candidate for the future than an older, smaller value.<\/li>\n\n\n\n
          3. Get the Max:<\/strong> The current maximum for the window is always at the front<\/strong> of the queue.<\/li>\n<\/ol>\n<\/details>\n\n\n\n
            \n\n\n\n
            Summary Table<\/h2>\n\n\n\n
            Problem Type<\/strong><\/td>Core Idea<\/strong><\/td>Best Complexity<\/strong><\/td><\/tr><\/thead>
            0\/1<\/strong><\/td>Each item used once<\/td>O(NW)<\/td><\/tr>
            Complete<\/strong><\/td>Infinite items, forward loop<\/td>O(NW)<\/td><\/tr>
            Bounded<\/strong><\/td>Finite count, Binary Splitting<\/td>O<\/mi>(<\/mo>N<\/mi>W<\/mi><\/mspace>log<\/mi>\u2061<\/mo><\/mrow>(<\/mo>max<\/mi>\u2061<\/mo><\/mspace><\/mrow>n<\/mi>i<\/mi><\/msub>)<\/mo>)<\/mo><\/mrow>O(NW \\log (\\max n_i))<\/annotation><\/semantics><\/math><\/td><\/tr>
            Bounded (Opt)<\/strong><\/td>Monotonic Queue<\/td>O(NW)<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
            \n\n\n\n
            Final Thoughts<\/h2>\n\n\n\n
            The Knapsack problem isn’t just about bags and gold; it’s about resource allocation<\/strong>. Whether you’re optimizing server load or a financial portfolio, these DP patterns are your best friends.<\/p>\n\n\n\n
            <\/p>\n","protected":false},"excerpt":{"rendered":"
            The Knapsack problem is the “Hello World” of Dynamic Programming. But beyond the basic 0\/1 version lies a world of clever optimizations and mathematical tricks. In this post, we\u2019ll break down the three major types and the patterns that solve them. 1. The Foundation: 0\/1 Knapsack The Rule: You have one of each item. You […]<\/p>\n","protected":false},"author":4,"featured_media":43,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8],"tags":[],"class_list":["post-53","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithm"],"_links":{"self":[{"href":"https:\/\/blog.mirpri.com\/index.php\/wp-json\/wp\/v2\/posts\/53","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.mirpri.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.mirpri.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.mirpri.com\/index.php\/wp-json\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.mirpri.com\/index.php\/wp-json\/wp\/v2\/comments?post=53"}],"version-history":[{"count":0,"href":"https:\/\/blog.mirpri.com\/index.php\/wp-json\/wp\/v2\/posts\/53\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blog.mirpri.com\/index.php\/wp-json\/wp\/v2\/media\/43"}],"wp:attachment":[{"href":"https:\/\/blog.mirpri.com\/index.php\/wp-json\/wp\/v2\/media?parent=53"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.mirpri.com\/index.php\/wp-json\/wp\/v2\/categories?post=53"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.mirpri.com\/index.php\/wp-json\/wp\/v2\/tags?post=53"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}