Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Fractional Knapsack

MEDIUMProblemSolveExternal Links

Description

You are given two arrays — val[] representing the value of each item and wt[] representing the weight of each item — along with an integer W representing the maximum capacity of a knapsack.

Your task is to select items to place into the knapsack such that the total value is maximized, without the total weight exceeding the capacity W.

Each item can either be included completely or excluded entirely — you cannot take a fraction of an item. Every item is available only once.

Examples

Example 1

Input: W = 4, val = [1, 2, 3], wt = [4, 5, 1]

Output: 3

Explanation: Item 0 weighs 4 (value 1) and item 2 weighs 1 (value 3). We cannot take both since 4 + 1 = 5 > 4. Taking item 2 alone gives value 3, while taking item 0 alone gives value 1. Item 1 weighs 5, which exceeds the capacity entirely. The maximum value is 3.

Example 2

Input: W = 3, val = [1, 2, 3], wt = [4, 5, 6]

Output: 0

Explanation: Every item weighs more than the knapsack capacity of 3. No item can be included, so the maximum value is 0.

Example 3

Input: W = 5, val = [10, 40, 30, 50], wt = [5, 4, 2, 3]

Output: 80

Explanation: Select item 2 (value 30, weight 2) and item 3 (value 50, weight 3). Total weight = 2 + 3 = 5 ≤ W. Total value = 30 + 50 = 80. No other combination of items yields a higher value within the weight limit.

Constraints

  • 1 ≤ val.size() = wt.size() ≤ 10^3
  • 1 ≤ W ≤ 10^3
  • 1 ≤ val[i] ≤ 10^3
  • 1 ≤ wt[i] ≤ 10^3

Editorial

Brute Force

Intuition

Imagine you are packing for a trip with a weight-limited suitcase. For each item on the table, you have a simple binary choice: put it in or leave it out. With just a few items, you could literally try every combination and pick the most valuable set that fits.

This is exactly what recursion does. Starting from the last item, we ask: what if we include this item? And what if we exclude it? For each choice, we recursively solve the smaller problem with the remaining items and adjusted capacity. We take whichever choice yields the higher value.

The key decision at each step:

  • Pick the item: Only possible if its weight does not exceed the remaining capacity. We add its value and reduce the capacity.
  • Skip the item: We move on to the next item with the same capacity.

We explore both paths and return the maximum.

Step-by-Step Explanation

Let's trace with val = [1, 2, 3], wt = [4, 5, 1], W = 4:

Step 1: Call K(4, 3). Consider item 2 (val=3, wt=1). Weight 1 ≤ 4, so we can pick or skip.

Step 2: Pick item 2: value = 3 + K(4-1, 2) = 3 + K(3, 2). Recurse with capacity 3 and 2 items left.

Step 3: At K(3, 2): item 1 has weight 5 > 3. Cannot pick! Only option is skip → K(3, 1).

Step 4: At K(3, 1): item 0 has weight 4 > 3. Cannot pick! Skip → K(3, 0) = 0 (base case).

Step 5: Bubble up: K(3, 1) = 0, K(3, 2) = 0. So the pick branch yields 3 + 0 = 3.

Step 6: Now explore the skip branch of K(4, 3): K(4, 2).

Step 7: At K(4, 2): item 1 has weight 5 > 4. Skip → K(4, 1).

Step 8: At K(4, 1): item 0 has weight 4 ≤ 4. Can pick!

  • Pick: val = 1 + K(0, 0) = 1 + 0 = 1
  • Skip: K(4, 0) = 0
  • K(4, 1) = max(1, 0) = 1

Step 9: K(4, 2) = 1. Skip branch of K(4, 3) yields 1.

Step 10: K(4, 3) = max(pick=3, skip=1) = 3. Taking item 2 alone is optimal.

Recursive Exploration — Pick or Skip Each Item — Watch the recursion tree unfold as we explore every possible pick/skip combination, drilling down to base cases and bubbling results back up.

Algorithm

  1. Define recursive function knapsack(W, n):
    • Base case: if n == 0 or W == 0, return 0
    • If wt[n-1] > W: item cannot fit, return knapsack(W, n-1)
    • Otherwise compute both options:
      • pick = val[n-1] + knapsack(W - wt[n-1], n-1)
      • skip = knapsack(W, n-1)
    • Return max(pick, skip)
  2. Call knapsack(W, n) where n is the total number of items

Code

#include <vector>
using namespace std;

class Solution {
public:
    int knapsackRec(int W, vector<int>& val, vector<int>& wt, int n) {
        if (n == 0 || W == 0)
            return 0;

        if (wt[n - 1] > W)
            return knapsackRec(W, val, wt, n - 1);

        int pick = val[n - 1] + knapsackRec(W - wt[n - 1], val, wt, n - 1);
        int skip = knapsackRec(W, val, wt, n - 1);

        return max(pick, skip);
    }

    int knapsack(int W, vector<int>& val, vector<int>& wt) {
        return knapsackRec(W, val, wt, wt.size());
    }
};
class Solution:
    def knapsack(self, W: int, val: list[int], wt: list[int]) -> int:
        def solve(W, n):
            if n == 0 or W == 0:
                return 0

            if wt[n - 1] > W:
                return solve(W, n - 1)

            pick = val[n - 1] + solve(W - wt[n - 1], n - 1)
            skip = solve(W, n - 1)

            return max(pick, skip)

        return solve(W, len(val))
class Solution {
    static int knapsackRec(int W, int[] val, int[] wt, int n) {
        if (n == 0 || W == 0)
            return 0;

        if (wt[n - 1] > W)
            return knapsackRec(W, val, wt, n - 1);

        int pick = val[n - 1] + knapsackRec(W - wt[n - 1], val, wt, n - 1);
        int skip = knapsackRec(W, val, wt, n - 1);

        return Math.max(pick, skip);
    }

    static int knapsack(int W, int[] val, int[] wt) {
        return knapsackRec(W, val, wt, wt.length);
    }
}

Complexity Analysis

Time Complexity: O(2^n)

In the worst case, every item can be either picked or skipped, giving 2 branches at each level of recursion. With n items, this creates up to 2^n recursive calls. Many of these calls solve the same subproblem repeatedly, but without caching, each is recomputed from scratch.

Space Complexity: O(n)

The recursion stack can go at most n levels deep (one level per item). No additional data structures are used.

Why This Approach Is Not Efficient

The recursive approach explores up to 2^n combinations. With n up to 10^3, that means up to 2^1000 operations — an astronomically large number that no computer could ever complete.

The root cause is overlapping subproblems. The same (remaining capacity, items left) pair gets computed multiple times along different branches of the recursion tree. For example, K(3, 1) might be reached by both the pick-and-skip and skip-and-pick paths. Each redundant computation wastes time exponentially.

Key insight: There are only n × W unique subproblems (each combination of items-remaining and capacity-remaining). If we store the result of each subproblem the first time we solve it and reuse it thereafter, we eliminate all redundant computation. This is the essence of Dynamic Programming. A 2D table of size (n+1) × (W+1) can store all subproblem answers, reducing the time from O(2^n) to O(n × W).

Better Approach - Dynamic Programming (Tabulation)

Intuition

Instead of top-down recursion, we build the solution bottom-up using a 2D table. We create a table dp[i][j] where each cell answers the question: "What is the maximum value I can achieve using the first i items with a knapsack capacity of j?"

We fill this table row by row. For each item and each possible capacity, we make the same pick-or-skip decision as the recursive approach:

  • Skip item i: The best value is whatever we achieved with the first i-1 items: dp[i-1][j].
  • Pick item i: Only if it fits (wt[i-1] ≤ j). The value is val[i-1] + dp[i-1][j - wt[i-1]] — the item's value plus the best we could do with the remaining capacity using the first i-1 items.

We take the maximum of these two choices.

The beauty of tabulation is that by the time we need dp[i-1][...], that entire row is already computed. No redundant work, no recursion stack — just a systematic table fill.

Step-by-Step Explanation

Let's trace with val = [10, 40, 30, 50], wt = [5, 4, 2, 3], W = 5:

We build a 5×6 table (4 items + 1 base row, capacities 0 through 5).

Step 1: Base case row: dp[0][j] = 0 for all j. With zero items, value is always 0.

Step 2: Row 1 — Item 0 (val=10, wt=5):

  • Capacities 0–4: Weight 5 doesn't fit. dp[1][0..4] = 0.
  • Capacity 5: dp[1][5] = max(skip=0, pick=10+dp[0][0]) = 10. Item 0 fills the entire knapsack.

Step 3: Row 2 — Item 1 (val=40, wt=4):

  • Capacity 4: dp[2][4] = max(skip=dp[1][4]=0, pick=40+dp[1][0]) = 40.
  • Capacity 5: dp[2][5] = max(skip=dp[1][5]=10, pick=40+dp[1][1]) = max(10, 40) = 40.

Step 4: Row 3 — Item 2 (val=30, wt=2):

  • Capacity 2: dp[3][2] = max(skip=0, pick=30+dp[2][0]) = 30.
  • Capacity 4: dp[3][4] = max(skip=dp[2][4]=40, pick=30+dp[2][2]=30) = 40. Skip wins!
  • Capacity 5: dp[3][5] = max(skip=dp[2][5]=40, pick=30+dp[2][3]=30) = 40.

Step 5: Row 4 — Item 3 (val=50, wt=3):

  • Capacity 3: dp[4][3] = max(skip=30, pick=50+dp[3][0]=50) = 50.
  • Capacity 5: dp[4][5] = max(skip=dp[3][5]=40, pick=50+dp[3][2]=50+30=80) = 80!

Result: dp[4][5] = 80. Items 2 and 3 combine optimally (weight 2+3=5, value 30+50=80).

Bottom-Up DP Table — Building the Optimal Solution Cell by Cell — Watch the DP table fill row by row. Each cell represents the best value achievable with a subset of items and a given capacity. Dependencies point to the cells used in the pick/skip decision.

Algorithm

  1. Create a 2D array dp of size (n+1) × (W+1), initialized to 0
  2. For each item i from 1 to n:
    • For each capacity j from 1 to W:
      • Set dp[i][j] = dp[i-1][j] (skip item i)
      • If wt[i-1] ≤ j:
        • dp[i][j] = max(dp[i][j], val[i-1] + dp[i-1][j - wt[i-1]])
  3. Return dp[n][W]

Code

#include <vector>
using namespace std;

class Solution {
public:
    int knapsack(int W, vector<int>& val, vector<int>& wt) {
        int n = wt.size();
        vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= W; j++) {
                dp[i][j] = dp[i - 1][j];
                if (wt[i - 1] <= j) {
                    dp[i][j] = max(dp[i][j],
                                   val[i - 1] + dp[i - 1][j - wt[i - 1]]);
                }
            }
        }

        return dp[n][W];
    }
};
class Solution:
    def knapsack(self, W: int, val: list[int], wt: list[int]) -> int:
        n = len(val)
        dp = [[0] * (W + 1) for _ in range(n + 1)]

        for i in range(1, n + 1):
            for j in range(1, W + 1):
                dp[i][j] = dp[i - 1][j]
                if wt[i - 1] <= j:
                    dp[i][j] = max(dp[i][j],
                                   val[i - 1] + dp[i - 1][j - wt[i - 1]])

        return dp[n][W]
class Solution {
    static int knapsack(int W, int[] val, int[] wt) {
        int n = wt.length;
        int[][] dp = new int[n + 1][W + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= W; j++) {
                dp[i][j] = dp[i - 1][j];
                if (wt[i - 1] <= j) {
                    dp[i][j] = Math.max(dp[i][j],
                                val[i - 1] + dp[i - 1][j - wt[i - 1]]);
                }
            }
        }

        return dp[n][W];
    }
}

Complexity Analysis

Time Complexity: O(n × W)

We fill a table with (n+1) rows and (W+1) columns. Each cell requires O(1) work (a comparison and possibly an addition). Total: O(n × W). With n, W up to 10^3, this is at most 10^6 operations — well within time limits.

Space Complexity: O(n × W)

The 2D DP table has (n+1) × (W+1) entries. For the given constraints, this is up to ~10^6 integers — manageable but not minimal.

Why This Approach Is Not Efficient

The tabulation approach achieves O(n × W) time, which is excellent. However, the space usage is O(n × W) — a full 2D table. With both n and W up to 10^3, this means storing up to 10^6 integers, consuming several megabytes of memory.

Key observation: When filling row i of the DP table, we only ever look at row i-1. Rows 0 through i-2 are never accessed again. Storing the entire table wastes memory on rows we will never revisit.

Insight: If we only need the previous row to compute the current row, we can collapse the entire 2D table into a single 1D array. By processing capacities from right to left within each item's iteration, we can update the array in-place without overwriting values we still need. This reduces space from O(n × W) to O(W).

Optimal Approach - Space-Optimized DP

Intuition

Think of the 2D DP table as a spreadsheet where each row represents adding one more item to our consideration set. When we fill row 4, we only look at row 3 — we never glance at rows 0, 1, or 2. So why keep them around?

We can replace the entire spreadsheet with a single row (a 1D array). After processing each item, the array stores the best values for all capacities considering items processed so far.

The crucial trick is the right-to-left update order. In the 0/1 knapsack, each item can be used at most once. If we updated left-to-right, when computing dp[5] we might use an already-updated dp[2] that reflects the current item — effectively using the same item twice. By going right-to-left, dp[j - wt[i]] still holds the value from the previous item's iteration, preserving the 0/1 constraint.

This single-row technique is a standard DP space optimization: same time complexity, dramatically less memory.

Step-by-Step Explanation

Using val = [10, 40, 30, 50], wt = [5, 4, 2, 3], W = 5:

Step 1: Initialize dp = [0, 0, 0, 0, 0, 0] (size W+1 = 6).

Step 2: Process Item 0 (val=10, wt=5). Right-to-left from j=5 to j=5:

  • j=5: dp[5] = max(0, 10+dp[0]) = 10.
  • dp = [0, 0, 0, 0, 0, 10]

Step 3: Process Item 1 (val=40, wt=4). Right-to-left from j=5 to j=4:

  • j=5: dp[5] = max(10, 40+dp[1]) = max(10, 40) = 40.
  • j=4: dp[4] = max(0, 40+dp[0]) = 40.
  • dp = [0, 0, 0, 0, 40, 40]

Step 4: Process Item 2 (val=30, wt=2). Right-to-left from j=5 to j=2:

  • j=5: dp[5] = max(40, 30+dp[3]) = max(40, 30) = 40. No change.
  • j=4: dp[4] = max(40, 30+dp[2]) = max(40, 30) = 40. No change.
  • j=3: dp[3] = max(0, 30+dp[1]) = 30.
  • j=2: dp[2] = max(0, 30+dp[0]) = 30.
  • dp = [0, 0, 30, 30, 40, 40]

Step 5: Process Item 3 (val=50, wt=3). Right-to-left from j=5 to j=3:

  • j=5: dp[5] = max(40, 50+dp[2]) = max(40, 80) = 80!
  • j=4: dp[4] = max(40, 50+dp[1]) = max(40, 50) = 50.
  • j=3: dp[3] = max(30, 50+dp[0]) = max(30, 50) = 50.
  • dp = [0, 0, 30, 50, 50, 80]

Result: dp[5] = 80.

Space-Optimized DP — Single Array Updated Right-to-Left — Watch a single 1D array transform as each item is processed. Right-to-left updates ensure we never use the same item twice.

Algorithm

  1. Create a 1D array dp of size W+1, initialized to 0
  2. For each item i from 0 to n-1:
    • For j from W down to wt[i] (right-to-left traversal):
      • dp[j] = max(dp[j], val[i] + dp[j - wt[i]])
  3. Return dp[W]

Code

#include <vector>
using namespace std;

class Solution {
public:
    int knapsack(int W, vector<int>& val, vector<int>& wt) {
        int n = wt.size();
        vector<int> dp(W + 1, 0);

        for (int i = 0; i < n; i++) {
            for (int j = W; j >= wt[i]; j--) {
                dp[j] = max(dp[j], val[i] + dp[j - wt[i]]);
            }
        }

        return dp[W];
    }
};
class Solution:
    def knapsack(self, W: int, val: list[int], wt: list[int]) -> int:
        n = len(val)
        dp = [0] * (W + 1)

        for i in range(n):
            for j in range(W, wt[i] - 1, -1):
                dp[j] = max(dp[j], val[i] + dp[j - wt[i]])

        return dp[W]
class Solution {
    static int knapsack(int W, int[] val, int[] wt) {
        int n = wt.length;
        int[] dp = new int[W + 1];

        for (int i = 0; i < n; i++) {
            for (int j = W; j >= wt[i]; j--) {
                dp[j] = Math.max(dp[j], val[i] + dp[j - wt[i]]);
            }
        }

        return dp[W];
    }
}

Complexity Analysis

Time Complexity: O(n × W)

For each of the n items, we iterate through up to W capacities. Each iteration does O(1) work (one comparison and one addition). Total: O(n × W), identical to the 2D tabulation approach.

Space Complexity: O(W)

We use a single 1D array of size W+1. No matter how many items there are, the space remains proportional only to the capacity. For W up to 10^3, this is just 1000 integers — a dramatic improvement over the O(n × W) = O(10^6) space of the 2D table.