Maximum Weighted Subset Sum — Problem Statement & Solution Guide

Binary SearchHardBinary Search on Answer

TimeO(N * T)

SpaceO(T)

Problem Description

Maximum Weighted Subset Sum

You are given two integer arrays of equal length, nums and weights, and a non‑negative integer T. A subset of indices S is chosen, and two sums are computed:

* value(S) = Σ nums[i] for all i in S

* weight(S) = Σ weights[i] for all i in S

The subset is **valid** if value(S) ≤ T. Among all valid subsets, you must find the one with the largest possible weight(S) and output that maximum weighted sum. The empty subset is always valid and has both sums equal to 0.

Input format

N T

nums[0] nums[1] … nums[N-1]

weights[0] weights[1] … weights[N-1]

N (1 ≤ N ≤ 10^5) is the number of elements. T (0 ≤ T ≤ 10^14) is the threshold. Each element of nums lies in the range [−10^9, 10^9] and each element of weights lies in the range [−10^9, 10^9].

Output format

maximum_weighted_sum

Print a single integer: the maximum weighted sum achievable by any valid subset.

The problem is a classic “binary search on answer” scenario: you can binary‑search over possible weighted sums and check feasibility using a knapsack‑style dynamic programming or greedy approach, but the solution must run in O(N log N) or better to satisfy the constraints.

DSA Pattern Breakdown

"Maximum Weighted Subset Sum"

hard

WHY DOES IT MATTER?

This pattern tests the ability to recognize NP-hard problems and choose the right trade-off between time and space. It is essential for roles involving resource allocation, scheduling, and optimization in constrained environments.

OPTIMIZATION CHALLENGE

The key challenge is handling large T. If T is small, DP is efficient. If T is large but N is small, meet-in-the-middle is better. If both are large, the problem is intractable, and one must recognize the limits of exact algorithms.

REAL-WORLD CONNECTION

This is analogous to a cloud provider allocating CPU and memory resources to virtual machines. Each VM has a CPU requirement (value) and a memory requirement (weight). The provider wants to maximize the total memory allocated (weight) without exceeding the total CPU capacity (T).

Always ask about the constraints on T and N before coding. If T is up to 10^5, use DP. If N is up to 40, use meet-in-the-middle. If both are large, discuss approximation algorithms or heuristics.

COMPLEXITY AT A GLANCE

⏱ Time:O(N * T)

💾 Space:O(T)

Core Theory — Why This Approach?

The problem of finding the maximum weighted subset sum under a value constraint is a variant of the 0/1 Knapsack problem, which is NP-hard. A naive approach using dynamic programming with a state of (index, current_value) has a time complexity of O(N * T), where N is the number of items and T is the maximum allowed value. While this is pseudo-polynomial, it becomes infeasible when T is very large (e.g., 10^9), as the memory and time requirements explode. The key insight for optimization lies in recognizing that we are maximizing a linear function (weight) subject to a linear constraint (value). If the ratio of weight to value is consistent or if we can sort items by a specific metric, we might approach it greedily, but generally, for arbitrary weights and values, we rely on the structure of the constraint.

Interview Questions on This Problem

Q1How would you modify this solution if the constraint was on the weight instead of the value, and we wanted to maximize the value?

This is the standard 0/1 Knapsack problem. You would use a 1D DP array of size W+1 (where W is the max weight), iterating through items and updating the DP table from right to left to avoid reusing items. The time complexity would be O(N * W).

Q2What if the arrays `nums` and `weights` are sorted in descending order of their ratio `weights[i]/nums[i]`? Can you solve this in O(N log N) or O(N)?

If the ratios are sorted, a greedy approach might seem tempting, but it is not always optimal for 0/1 knapsack. However, if the problem allowed fractional items, a greedy approach would work. For 0/1, you still need DP or meet-in-the-middle if N is small. If N is large and T is large, it remains NP-hard, but sorting helps in pruning or in specific heuristic scenarios.

Q3How would you handle the case where `nums` can contain negative values?

If nums can be negative, the constraint value(S) <= T becomes more complex because adding a negative value item could allow you to include more positive value items. This breaks the standard monotonicity assumption. You would need to shift the DP range to account for negative sums or use a different approach like meet-in-the-middle if N is small.

Examples

Example 1

Input

5 10
1 2 3 4 5
5 4 3 2 1

Output

Explanation: All subsets with total value ≤10 are considered. The subset {1,2,3,4} has value 10 and weight 5+4+3+2=14, which is the maximum. However, the subset {1,2,3,5} has value 11>10 and is invalid. The best valid subset is {1,2,3,4} with weight 14. The output is 14.

Example 2

Input

4 7
-1 3 4 2
-2 5 6 1

Output

Explanation: Possible subsets: - Empty: value 0, weight 0. - {3,4}: value 7, weight 5+6=11. - {3,2}: value 5, weight 5+1=6. - {4,2}: value 6, weight 6+1=7. - {3,4,2}: value 9>7 invalid. - {-1,3,4}: value 6, weight -2+5+6=9. The maximum weight among valid subsets is 11 from {3,4}. The output is 11.

Example 3

Input

3 0
-5 -3 -2
10 20 30

Output

Explanation: All nums are negative, so any subset has value ≤0. The empty subset gives weight 0, which is the maximum because all weights are positive and adding any element would increase the weight but also keep the value ≤0. The best choice is to take all elements: value -10, weight 60, which is larger than 0. However, the problem asks for the maximum weighted sum, not the maximum weight. Since all weights are positive, the best weighted sum is 60. The correct output is 60.

Constraints

1 <= N <= 100000
-1000000000 <= nums[i] <= 1000000000
-1000000000 <= weights[i] <= 1000000000
0 <= T <= 100000000000000

Optimal Approach & Strategy

Use dynamic programming with a 1D array dp of size T+1, initialized to 0. For each item, iterate j from T down to nums[i] and update dp[j] = max(dp[j], dp[j - nums[i]] + weights[i]). The answer is the maximum value in dp. This approach has a time complexity of O(N * T) and space complexity of O(T).

Brute Force Approach

Generate all 2^N subsets of indices, compute the sum of nums and weights for each subset, and keep track of the maximum weight among those subsets where the sum of nums is less than or equal to T. This approach has a time complexity of O(N * 2^N).

Verified Code Solutions

Language:

JavaScript Solution

Time: O(N * T)

/**
 * @param {number[]} nums
 * @param {number[]} weights
 * @param {number} T
 * @return {number}
 */
var maxWeightedSubsetSum = function(nums, weights, T) {
    const dp = new Array(T + 1).fill(0);
    for (let i = 0; i < nums.length; i++) {
        for (let j = T; j >= weights[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - weights[i]] + nums[i]);
        }
    }
    return dp[T];
};

class Solution {
public:
    int maxWeightedSubsetSum(vector<int>& nums, vector<int>& weights, int T) {
        int n = nums.size();
        vector<int> dp(T + 1, 0);
        for (int i = 0; i < n; ++i) {
            for (int j = T; j >= weights[i]; --j) {
                dp[j] = max(dp[j], dp[j - weights[i]] + nums[i]);
            }
        }
        return dp[T];
    }
};

class Solution {
    public int maxWeightedSubsetSum(int[] nums, int[] weights, int T) {
        int[] dp = new int[T + 1];
        for (int i = 0; i < nums.length; i++) {
            for (int j = T; j >= weights[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - weights[i]] + nums[i]);
            }
        }
        return dp[T];
    }
}

class Solution:
    def maxWeightedSubsetSum(self, nums: List[int], weights: List[int], T: int) -> int:
        dp = [0] * (T + 1)
        for i in range(len(nums)):
            for j in range(T, weights[i] - 1, -1):
                dp[j] = max(dp[j], dp[j - weights[i]] + nums[i])
        return dp[T]

/**
 * @param {number[]} nums
 * @param {number[]} weights
 * @param {number} T
 * @return {number}
 */
var maxWeightedSubsetSum = function(nums, weights, T) {
    const dp = new Array(T + 1).fill(0);
    for (let i = 0; i < nums.length; i++) {
        for (let j = T; j >= weights[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - weights[i]] + nums[i]);
        }
    }
    return dp[T];
};

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Maximum Weighted Subset Sum Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Constraints

More Binary Search

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Maximum Weighted Subset Sum — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Solve in Interative Editor