Problem

You are given a knapsack capacity W and n gold bars with weights w[0..n-1]. Each bar can be taken at most once (no repetitions, no fractional taking). Every bar’s value equals its weight. Select a subset of bars whose total weight does not exceed W and is as large as possible. Return that maximum achievable weight.

This is the 0-1 Knapsack Problem specialized to the case value[i] = weight[i]. In this special case, maximizing total value is equivalent to maximizing total weight—so it also aligns with the optimization version of the classic Subset Sum Problem (find the largest sum ≤ W).

Input / Output

  • Input: capacity W, number of bars n, followed by the n weights.
  • Output: the largest total weight ≤ W obtainable using each bar at most once.

Examples

Example 1

1
2
3
4
5

Input:
W = 10, n = 3
weights = [1, 4, 8]
Output: 9
Explanation: Best subset is {1, 8} totaling 9 (cannot reach 10 exactly).

Relation to Other Problems

  • General 0-1 Knapsack: This is the case where values == weights.
  • Subset Sum (decision): asks if we can reach exactly W; here we seek the maximum ≤ W.
  • Partition Equal Subset Sum: special subset sum aiming for total/2.
Similar Problems

Solution

Let dp[i][c] = maximum achievable weight ≤ c using the first i items. Since value = weight, transition only adds weight.

Method 1 - Naive Recursion (Exponential)

Intuition

For each item decide: include it (if it fits) or exclude it. Explore all subsets; track best sum ≤ W.

Approach

Recursive function solve(i, remaining) returns best weight using items i..n-1 with capacity remaining:

  1. If i == n or remaining == 0: return 0.
  2. Option 1: skip -> skip = solve(i+1, remaining).
  3. Option 2: take if w[i] ≤ remaining -> take = w[i] + solve(i+1, remaining - w[i]).
  4. Return max(skip, take).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

#include <vector>
using namespace std;

long long maxGoldRec(const vector<int>& w, int i, int cap) {
    if (i == (int)w.size() || cap == 0) return 0;
    long long skip = maxGoldRec(w, i+1, cap);
    if (w[i] > cap) return skip;
    long long take = w[i] + maxGoldRec(w, i+1, cap - w[i]);
    return max(skip, take);
}
long long takeMaxGoldRec(const vector<int>& w, int W) { return maxGoldRec(w, 0, W); }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

package main

func maxGoldRec(w []int, i, cap int) int {
    if i == len(w) || cap == 0 { return 0 }
    skip := maxGoldRec(w, i+1, cap)
    if w[i] > cap { return skip }
    take := w[i] + maxGoldRec(w, i+1, cap-w[i])
    if take > skip { return take }
    return skip
}
func TakeMaxGoldRec(w []int, W int) int { return maxGoldRec(w, 0, W) }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

import java.util.*;
class GoldRec {
    int dfs(int[] w, int i, int cap) {
        if (i == w.length || cap == 0) return 0;
        int skip = dfs(w, i+1, cap);
        if (w[i] > cap) return skip;
        int take = w[i] + dfs(w, i+1, cap - w[i]);
        return Math.max(skip, take);
    }
    int takeMaxGold(int[] w, int W) { return dfs(w, 0, W); }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

from typing import List

def _gold_rec(w: List[int], i: int, cap: int) -> int:
    if i == len(w) or cap == 0:
        return 0
    skip = _gold_rec(w, i+1, cap)
    if w[i] > cap:
        return skip
    take = w[i] + _gold_rec(w, i+1, cap - w[i])
    return max(skip, take)

def take_max_gold_rec(w: List[int], W: int) -> int:
    return _gold_rec(w, 0, W)

Complexity

  • ⏰ Time complexity: O(2^n) – explores all subsets.
  • 🧺 Space complexity: O(n) – recursion depth.

Method 2 - Top-Down Memoization

Intuition

Store results for (i, cap) to avoid re-exploring the same state.

Approach

Use 2D memo array (size n x (W+1)) initialized to -1. Standard recursion; fill memo.

Recurrence

F(i, c) = max(F(i+1, c), w[i] + F(i+1, c - w[i])) if w[i] ≤ c, else F(i, c) = F(i+1, c).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

#include <vector>
long long dfsMemo(const std::vector<int>& w, int i, int cap, std::vector<std::vector<long long>>& memo){
    if (i == (int)w.size() || cap == 0) return 0;
    long long &res = memo[i][cap];
    if (res != -1) return res;
    long long skip = dfsMemo(w, i+1, cap, memo);
    if (w[i] > cap) return res = skip;
    long long take = w[i] + dfsMemo(w, i+1, cap - w[i], memo);
    return res = max(skip, take);
}
long long takeMaxGoldMemo(const std::vector<int>& w, int W){
    std::vector<std::vector<long long>> memo(w.size(), std::vector<long long>(W+1, -1));
    return dfsMemo(w, 0, W, memo);
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func TakeMaxGoldMemo(w []int, W int) int {
    memo := make([][]int, len(w))
    for i := range memo { memo[i] = make([]int, W+1); for c := 0; c <= W; c++ { memo[i][c] = -1 } }
    var dfs func(int,int) int
    dfs = func(i, cap int) int {
        if i == len(w) || cap == 0 { return 0 }
        if memo[i][cap] != -1 { return memo[i][cap] }
        skip := dfs(i+1, cap)
        if w[i] > cap { memo[i][cap] = skip; return skip }
        take := w[i] + dfs(i+1, cap-w[i])
        if take > skip { memo[i][cap] = take } else { memo[i][cap] = skip }
        return memo[i][cap]
    }
    return dfs(0, W)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class GoldMemo {
    int[][] memo;
    int dfs(int[] w, int i, int cap) {
        if (i == w.length || cap == 0) return 0;
        if (memo[i][cap] != -1) return memo[i][cap];
        int skip = dfs(w, i+1, cap);
        if (w[i] > cap) return memo[i][cap] = skip;
        int take = w[i] + dfs(w, i+1, cap - w[i]);
        return memo[i][cap] = Math.max(skip, take);
    }
    int takeMaxGold(int[] w, int W) {
        memo = new int[w.length][W+1];
        for (int i = 0; i < w.length; i++) java.util.Arrays.fill(memo[i], -1);
        return dfs(w, 0, W);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

from functools import lru_cache
from typing import List

def take_max_gold_memo(w: List[int], W: int) -> int:
    @lru_cache(None)
    def f(i: int, cap: int) -> int:
        if i == len(w) or cap == 0:
            return 0
        skip = f(i+1, cap)
        if w[i] > cap:
            return skip
        take = w[i] + f(i+1, cap - w[i])
        return max(skip, take)
    return f(0, W)

Complexity

  • ⏰ Time complexity: O(n * W) – each (i, cap) solved once.
  • 🧺 Space complexity: O(n * W) – memo + recursion stack O(n).

Method 3 - Bottom-Up 2D DP

Intuition

Tabulate solutions for increasing number of items and capacities.

Approach

dp[i][c] = best weight using first i items with capacity c. Transition: if w[i-1] ≤ c, dp[i][c] = max(dp[i-1][c], w[i-1] + dp[i-1][c - w[i-1]]) else copy dp[i-1][c].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

#include <vector>
long long takeMaxGoldBU2D(const std::vector<int>& w, int W){
    int n = (int)w.size();
    std::vector<std::vector<long long>> dp(n+1, std::vector<long long>(W+1, 0));
    for (int i = 1; i <= n; ++i){
        for (int c = 0; c <= W; ++c){
            dp[i][c] = dp[i-1][c];
            if (w[i-1] <= c){
                dp[i][c] = std::max(dp[i][c], (long long)w[i-1] + dp[i-1][c - w[i-1]]);
            }
        }
    }
    return dp[n][W];
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func TakeMaxGoldBU2D(w []int, W int) int {
    n := len(w)
    dp := make([][]int, n+1)
    for i := range dp { dp[i] = make([]int, W+1) }
    for i := 1; i <= n; i++ {
        for c := 0; c <= W; c++ {
            dp[i][c] = dp[i-1][c]
            if w[i-1] <= c {
                cand := w[i-1] + dp[i-1][c-w[i-1]]
                if cand > dp[i][c] { dp[i][c] = cand }
            }
        }
    }
    return dp[n][W]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class GoldBU2D {
    int takeMaxGold(int[] w, int W) {
        int n = w.length;
        int[][] dp = new int[n+1][W+1];
        for (int i = 1; i <= n; i++) {
            for (int c = 0; c <= W; c++) {
                dp[i][c] = dp[i-1][c];
                if (w[i-1] <= c) {
                    dp[i][c] = Math.max(dp[i][c], w[i-1] + dp[i-1][c - w[i-1]]);
                }
            }
        }
        return dp[n][W];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def take_max_gold_bu_2d(w, W):
    n = len(w)
    dp = [[0]*(W+1) for _ in range(n+1)]
    for i in range(1, n+1):
        wi = w[i-1]
        for c in range(W+1):
            dp[i][c] = dp[i-1][c]
            if wi <= c:
                cand = wi + dp[i-1][c-wi]
                if cand > dp[i][c]:
                    dp[i][c] = cand
    return dp[n][W]

Complexity

  • ⏰ Time complexity: O(n * W) – nested loops.
  • 🧺 Space complexity: O(n * W) – 2D table.

Method 4 - Bottom-Up 1D Space Optimization

Intuition

Transition for current item depends only on previous row; iterate capacity descending to avoid reuse of an item twice.

Approach

  1. dp[c] = best weight for capacity c.
  2. For each item wi, loop c from W down to wi updating dp[c] = max(dp[c], wi + dp[c - wi]).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

#include <vector>
long long takeMaxGoldBU1D(const std::vector<int>& w, int W){
    std::vector<long long> dp(W+1, 0);
    for (int wi : w){
        for (int c = W; c >= wi; --c){
            dp[c] = std::max(dp[c], (long long)wi + dp[c - wi]);
        }
    }
    return dp[W];
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func TakeMaxGoldBU1D(w []int, W int) int {
    dp := make([]int, W+1)
    for _, wi := range w {
        for c := W; c >= wi; c-- {
            cand := wi + dp[c-wi]
            if cand > dp[c] { dp[c] = cand }
        }
    }
    return dp[W]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class GoldBU1D {
    int takeMaxGold(int[] w, int W) {
        int[] dp = new int[W+1];
        for (int wi : w) {
            for (int c = W; c >= wi; c--) {
                dp[c] = Math.max(dp[c], wi + dp[c - wi]);
            }
        }
        return dp[W];
    }
}
1
2
3
4
5
6
7
8

def take_max_gold_bu_1d(w, W):
    dp = [0]*(W+1)
    for wi in w:
        for c in range(W, wi-1, -1):
            cand = wi + dp[c-wi]
            if cand > dp[c]:
                dp[c] = cand
    return dp[W]

Complexity

  • ⏰ Time complexity: O(n * W) – same state count.
  • 🧺 Space complexity: O(W) – single array.

Method Comparison

Method Time Space Notes
1 Naive Recursion O(2^n) O(n) Exponential baseline
2 Memoized O(n * W) O(n * W) Practical top-down
3 Bottom-Up 2D O(n * W) O(n * W) Classic tabulation
4 Bottom-Up 1D O(n * W) O(W) Preferred optimized

Notes

  • If you need to reconstruct which bars are chosen, store predecessor info (e.g., keep a separate take[i][c] boolean in the 2D version, then backtrack). For the 1D optimized version, reconstruct by re-running with reverse reasoning or keeping additional tracking.
  • Because value equals weight, returns are always ≤ W and monotonic in W.
  • This file links to the general 0-1 Knapsack Problem for the broader formulation with independent value array.