Backpacking Problem Variation via Greedy Approach: How Many Apples Can You Put into the Basket?

You have some apples, where arr[i] is the weight of the i-th apple. You also have a basket that can carry up to 5000 units of weight. Return the maximum number of apples you can put in the basket.

Example 1:
Input: arr = [100,200,150,1000]
Output: 4
Explanation: All 4 apples can be carried by the basket since their sum of weights is 1450.

Example 2:
Input: arr = [900,950,800,1000,700,800]
Output: 5
Explanation: The sum of weights of the 6 apples exceeds 5000 so we choose any 5 of them.

Constraints:
1 <= arr.length <= 10^3
1 <= arr[i] <= 10^3

This is a simple variation of the back-packing problems. You are given the weight of each items, and you know the maximum capacity of the bag which is 5000 units. Then, you need to know the maximum items you can put.

Greedy Approach: by Sorting to Pick the Most Items

We can sort the items/apples by weights, in the ascending order. The time complexity via sorting is O(N.LogN). Then, we can follow the greedy strategy to pick the least weighted item at a time, until the total weights exceed the maximum.

The greedy approach works, because if you pick a heavier item, you can always pick a lighter one, which will not be a worse solution (you have more remaining capacity for extra items)

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

class Solution {
public:
    int maxNumberOfApples(vector<int>& arr) {
        sort(begin(arr), end(arr));
        int r = 0, curSum = 0;
        for (int i = 0; i < arr.size(); ++ i) {
            if (curSum + arr[i] <= 5000) {
                r ++;
                curSum += arr[i];
            } else {
                break;
            }
        }
        return r;
    }
};

class Solution {
public:
    int maxNumberOfApples(vector<int>& arr) {
        sort(begin(arr), end(arr));
        int r = 0, curSum = 0;
        for (int i = 0; i < arr.size(); ++ i) {
            if (curSum + arr[i] <= 5000) {
                r ++;
                curSum += arr[i];
            } else {
                break;
            }
        }
        return r;
    }
};

The above greedy solution runs at O(N.LogN) time overall. Another similar implementation in C++ saving up a variable.

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

class Solution {
public:
    int maxNumberOfApples(vector<int>& arr) {
        sort(begin(arr), end(arr));
        for (int i = 0, res = 0; i < arr.size(); ++ i) {
            if (res + arr[i] <= 5000) {
                res += arr[i];
            } else {
                return i;
            }
        }
        return arr.size();
    }
};

class Solution {
public:
    int maxNumberOfApples(vector<int>& arr) {
        sort(begin(arr), end(arr));
        for (int i = 0, res = 0; i < arr.size(); ++ i) {
            if (res + arr[i] <= 5000) {
                res += arr[i];
            } else {
                return i;
            }
        }
        return arr.size();
    }
};

You may also like the following relevant article: Algorithms Series: 0/1 BackPack – Dynamic Programming and BackTracking

–EOF (The Ultimate Computing & Technology Blog) —