PVsNPSolver's blog

Can this commonly asked interview problem be solved for tighter constraints?
By PVsNPSolver, history, 4 years ago, In English

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?

  • Vote: I like it
  • -16
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
4 years ago, hide # |
 
Vote: I like it +17 Vote: I do not like it

1 ≤ n ≤ 42

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.

→ Reply
  • »
    »
    9 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Indeed came across this question in OA.

    Thanks yeputons for the approach. Here's the code using meet in the middle + binary search:

    #include <bits/stdc++.h>
using namespace std;

typedef long long ll;

void getSubsetSums(vector<int>& nums, vector<ll>& sums) {
    int n = nums.size();
    int total = 1 << n;
    for (int i = 0; i < total; i++) {
        ll sum = 0;
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) sum += nums[j];
        }
        sums.push_back(sum);
    }
}

int maxBarbellWeight(vector<int>& weights, int maxCapacity) {
    int n = weights.size();
    int mid = n / 2;

    vector<int> left(weights.begin(), weights.begin() + mid);
    vector<int> right(weights.begin() + mid, weights.end());

    vector<ll> leftSums, rightSums;
    getSubsetSums(left, leftSums);
    getSubsetSums(right, rightSums);

    sort(rightSums.begin(), rightSums.end());

    ll best = 0;
    for (ll sumL : leftSums) {
        if (sumL > maxCapacity) continue;
        ll rem = maxCapacity - sumL;

        auto it = upper_bound(rightSums.begin(), rightSums.end(), rem);
        if (it != rightSums.begin()) {
            --it;
            ll sumR = *it;
            best = max(best, sumL + sumR);
        }
    }
    return best;
}

int main() {
    vector<int> weights = {7, 1, 5, 6, 2};
    int maxCapacity = 7;
    cout << maxBarbellWeight(weights, maxCapacity) << endl;
    return 0;
}
    → Reply