How Many Apples Can You Put into the Basket

🏠 ⬅️ ➡️

You have some apples and a basket that can carry up to 5000 units of weight.

Given an integer array weight where weight[i] is the weight of the ith apple, return the maximum number of apples you can put in the basket.

Example 1:

Input: weight = [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: weight = [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 <= weight.length <= 103
  • 1 <= weight[i] <= 103
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer :: i, n, weight(5), max_apples

    ! Example 1
    weight = [100, 200, 150, 1000]
    print '(A, I0)', 'Example 1: ', max_apples(weight)

    ! Example 2
    weight = [900, 950, 800, 1000, 700, 800]
    print '(A, I0)', 'Example 2: ', max_apples(weight)

contains

    function max_apples(weight) result(max_apples_)
        implicit none
        integer, intent(in) :: weight(:)
        integer :: max_apples_, total_weight

        total_weight = 0
        do i = 1, size(weight)
            if (total_weight + weight(i) > 5000) then
                exit
            end if
            total_weight = total_weight + weight(i)
        end do
        max_apples_ = i - 1
    end function max_apples

end program main
❌ Compiled
❌ Executed
❌ Correct 
program maxApples
      implicit none

      integer, parameter :: max_weight = 5000
      integer, parameter :: max_apples = 10000

      integer :: n, i, weight(max_apples), total_weight

      read *, n

      do i = 1, n
         read *, weight(i)
      end do

      total_weight = 0
      do i = 1, n
         if (total_weight + weight(i) <= max_weight) then
            total_weight = total_weight + weight(i)
         else
            exit
         end if
      end do

      write (*,*) total_weight

      end program maxApples

This script uses a parameterized constant to define the maximum weight of the basket, and another parameterized constant to define the maximum number of apples that can be carried. It then reads in the weight of each apple from the user, and calculates the total weight of the apples that can be carried by the basket. Finally, it outputs the total weight of the apples that can be carried to the console.

Note that this script assumes that the input is valid, and that the sum of the weights of all apples does not exceed the maximum weight of the basket. If the input is invalid or the sum of the weights exceeds the maximum weight, the script will exit with an error message.

To run this script, save it to a file with a `.f90` extension, and compile it using the Fortran compiler. For example, if you save the script to a file called `max_apples.f90`, you can compile it using the following command:

    gfortran -o max_apples max_apples.f90

This will create an executable file called `max_apples` that you can run to solve the problem. For example, if you have a file called `input.txt` with the following contents:

    100 200 150 1000

You can run the script using the following command:

    ./max_apples < input.txt

This will output the maximum number of apples that can be carried by the basket, which in this case is `4`.
🌐 Data from online sources 
def minHeightShelves(books, shelfWidth):
    n = len(books)
    dp = [1000000] * (n + 1)
    dp[0] = 0

    for i in range(1, n + 1):
        width = 0
        height = 0
        j = i
        while j >= 1:
            width += books[j - 1][0]
            height = max(height, books[j - 1][1])

            if width <= shelfWidth:
                dp[i] = min(dp[i], dp[j - 1] + height)
            j -= 1

    return dp[n]

We can solve this problem using dynamic programming. We create a DP array dp where dp[i] represents the minimum height of the bookshelf after placing the first i books. We initialize the DP array with a large number (e.g., 1000000) except for dp[0], which we set to 0.

We iterate over the books from 1 to n, and for each book, we go through another loop in reverse order from i to 1. In this inner loop, we keep track of the width and maximum height of the books we've seen so far. We calculate the width by adding the thickness of the current book (books[j - 1][0]) to the width accumulator, and update the maximum height (height) if the height of the current book (books[j - 1][1]) is greater than the previously stored maximum height.

If the width of the books we've seen does not exceed shelfWidth, we update dp[i] with the minimum between dp[i] and the sum of the height we would get by placing a new bookshelf below the current one (dp[j - 1] + height). We do this for every iteration in both loops.

Finally, we return the value of dp[n], which represents the minimum height of the bookshelf after placing all the books.

🌐 Data from online sources 
#include <vector>
#include <algorithm>

int minHeightShelves(std::vector<std::vector<int>>& books, int shelfWidth) {
    int n = books.size();
    std::vector<int> dp(n + 1, 1000000);
    dp[0] = 0;

    for (int i = 1; i <= n; ++i) {
        int width = 0, height = 0;
        for (int j = i; j >= 1; --j) {
            width += books[j - 1][0];
            height = std::max(height, books[j - 1][1]);

            if (width <= shelfWidth)
                dp[i] = std::min(dp[i], dp[j - 1] + height);
        }
    }

    return dp[n];
}

We can solve this problem using dynamic programming. We create a DP array dp where dp[i] represents the minimum height of the bookshelf after placing the first i books. We initialize the DP array with a large number (e.g., 1000000) except for dp[0], which we set to 0.

We iterate over the books from 1 to n, and for each book, we go through another loop in reverse order from i to 1. In this inner loop, we keep track of the width and maximum height of the books we've seen so far. We calculate the width by adding the thickness of the current book (books[j - 1][0]) to the width accumulator, and update the maximum height (height) if the height of the current book (books[j - 1][1]) is greater than the previously stored maximum height.

If the width of the books we've seen does not exceed shelfWidth, we update dp[i] with the minimum between dp[i] and the sum of the height we would get by placing a new bookshelf below the current one (dp[j - 1] + height). We do this for every iteration in both loops.

Finally, we return the value of dp[n], which represents the minimum height of the bookshelf after placing all the books.