Backpacking Problem Variation via Greedy Approach: How Many Appl

  • 时间:2020-09-18 17:39:21
  • 分类:网络文摘
  • 阅读:89 次

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) —

推荐阅读:
Compute the Total Hamming Distance between All Pairs of Integers  The Monotone Queue Implementation in Python  The Monotone Stack Implementation in Python  5 Killer WordPress SEO Plugins You Might Not Have Heard Of  How To Turn Your Daily Life Into Content  Partnering With Non-Profits Is a Great Way to Promote Your Blog  How to Raise Your Instagram Game for Your Blog  Young Inspirational Blogger Passes Away After Short Cancer Battl  4 Remote Working Benefits Bloggers Enjoy  How to Get Your Blog to be Ranked like a Leading Brand in 2017 
评论列表
添加评论