Как найти минимальное количество поездок, чтобы выполнить эту работу из точки А в точку Б, используя javascript?

Question

Итак, я решаю эту проблему, заданную как:

Есть мешки с весом от 1 до 3 единиц и я должен нести их из точки А в точку Б. Веса мешков даны в массиве. Все веса меньше 3 единиц.

      weights = [1, 1.78, 2.2, 2.73, 3]

Поэтому я должен совершать поездки с сумками, которые не должны пересекать общий вес более 3 единиц. Для этого я должен совершить минимальное количество поездок.

Пример: веса = [1,01, 1,99, 2,5, 1,5, 1,01]

Я могу нести все сумки минимум за 3 поездки, так как:

[1,01 + 1,99, 2,5, 1,5 + 1,01].

Значит, как определить минимальный номер. поездок, чтобы перевезти весовые мешки из пункта А в пункт Б?

Какую логику можно применить?

Answer 1

Один из подходов состоит в том, чтобы пройтись по отсортированному списку и всегда сначала выбирать наибольшее число.

Затем вы перебираете оставшиеся элементы и комбинируете их с наибольшим числом, где общая сумма меньше вашей цели.

Поскольку самое большое число всегда должно быть самым сложным для «спаривания», это должно дать вам оптимальное количество поездок.

Однако этот подход не распределяет вес равномерно. Это будет способствовать максимально возможной упаковке пар.

Вот простая реализация:

Answer 2

Здесь я использовал жадный подход, который заключается в сортировке массива весов и объединении самого тяжелого с самым легким и легким, пока мы не достигнем предела. Код Python:

      
def solve(A):
    A.sort()  
    n = len(A)
    i =0
    j = n-1
    ans=0
    while i<=j: 
        while A[i]+A[j] <=3: 
            i+=1
        ans+=1
        j-=1
  
    return ans 

print(solve([1.01, 1.99, 2.5, 1.5, 1.01]))

Временная сложность: O(n)