An athlete is lifting weights. The maximum capacity of the barbell is maxCapacity. Each barbell plate has a weight, weight[i]. Determine the maximum weight of plates that can be added to the barbell without exceeding maxCapacity.
Example
weights = [7, 1, 5, 6, 2]
maxCapacity = 7
There are 3 ways to reach the maximum weight: {7}, {1, 6} and {2, 5}. Other combinations are either more or less than 7 combined weight. Return 7.
Constraints
1 ≤ n ≤ 42 1 ≤ maxCapacity ≤ 10^9 1 ≤ weights[i][ ]≤ 10^9
Solution for 1e6 or 10^6 constraints:
int weightCapacity(vector<int> &weights, int maxCapacity) {
int n = weights.size();
vector<bool> dp(maxCapacity+1, false);
dp[0] = true;
int maxW = 0;
for(int i = 0; i < n; ++i)
{
for(int j = maxCapacity-weights[i]; j>=0; --j)
{
// Traversal in reverse order , The new state does not interfere with the old state to be traversed
if(dp[j])// j Weight status exists
{
dp[j+weights[i]] = true;
maxW = max(maxW, j+weights[i]);
}
}
}
return maxW;
}
How can we use binary search here for the tighter constraints. I understand the monotonicity but how do we check whether such a subsequence exists in the array that sums up to the mid weight?
This suggests some kind of bruteforce or other exponential dependency on
n. Meet-in-the-middle bruteforce should work: $$$2^{21}$$$ is about 2 million options, so one can generate all options for each half, sort them, and then use two pointers.