Отсортировать список чисел по парам, имея ограничение по их сумме

Question

Задание:
На берегу реки стояли n рыбаков, все они хотели перебраться на другой берег. Одна лодка может выдержать не более m килограмм, при этом в лодку помещается не более 2 человек. Определите, какое минимальное число лодок нужно, чтобы перевезти на другой берег всех рыбаков Программа должна вывести одно число - минимальное количество лодок, необходимое для переправки всех рыбаков на противоположный берег.

Я пока не додумался, как отсортировать по 2 рыбакам в лодку. Мой код считает усредненно и, часто, даёт верный ответ.

import math

big_man = 0   # вес рыбаков, которые не смогут переплыть (вес больше грузоподъемности лодки)
man = []

m = int(input("Максимальная масса, которую выдержит 1 лодка: "))
if 1 > m > 10e6:
    print("Неверное значение массы!")
else:
    n = int(input("Кол-во рыбаков: "))
    if 1 > n > 100:
        print("Недопустимое значение количества рыбаков!")
    else:
        kg = list(map(int, input("вес каждого рыбака через пробел: ").split()))
        count = len(kg)
        if count != n:
            print("Недопустимое количество веса!")
        else:
            for i in kg:
                if i > m:
                    big_man += 1
                else:
                    man.append(i)
            min_boat = math.ceil(sum(man)/m)
    if big_man > 0:
        print(f"{big_man} рыбака не смогут переплыть!")
        print(f"Смогут переплыть на другой берег оставшиеся {n - big_man} рыбака на {min_boat} лодках!")
    else:
        print(f"Смогут переплыть рыбаки на {min_boat} лодках!")

Answer 1

Я немного упростил условие для того, чтоб не загромождать код вводом и проверкой. Моё видение решения (готовый скрипт для запуска):

'''
На берегу реки стояли n (пусть будет 100) рыбаков, все они хотели перебраться на другой берег.
Одна лодка может выдержать не более m (пусть будет 100) килограмм, при этом в лодку помещается не более 2 человек.
Определите, какое минимальное число лодок нужно, чтобы перевезти на другой берег всех рыбаков.
'''

import os
import random

def min_boats(weights, max_weight):
    # Сортируем веса рыбаков по возрастанию:
    weights.sort()
    i, j = 0, len(weights) - 1
    boats = 0

    # Используем два указателя для подбора пар рыбаков:
    while i <= j:
        # Если два рыбака могут переправиться вместе, увеличиваем левый указатель:
        if weights[i] + weights[j] <= max_weight:
            i += 1
        # В любом случае, уменьшаем правый указатель и увеличиваем счетчик лодок:
        j -= 1
        boats += 1

    return boats

# Пример использования:

print("-" * 70 + "\nРасчёт минимального количества лодок для перевозки:\n" + "-" * 70)

n = 100
max_weight = 100
# Генерируем случайные веса для 100 рыбаков:
weights = [random.randint(1, 100) for _ in range(n)]

# Выводим минимальное количество лодок:
print(f"Минимальное количество лодок: {min_boats(weights, max_weight)}")

print("\nНажмите любую клавишу для продолжения...")
os.system("pause > nul" if os.name == "nt" else "read > /dev/null")

БЛОГ НА HUSL

Отсортировать список чисел по парам, имея ограничение по их сумме

Ответы (1 шт):