Вычисление максимального количества людей в лифте

#алгоритм #сложность

Дано список людей с именем и весом, максимальный вес который выдержит лифт. Вычислить
максимальное количество людей, которое может поместиться в лифт и вывести их список.

Не понимаю, как определить комбинацию людей которые могут быть. Ведь может быть разные
комбинации, 1, 2, 3 или 1, 2, 4, или 1, 3, 5, 6.
Хочу сначала узнать все возможные комбинации вместимых людей и потом выводить максимальное.
Но как узнать комбинации этих людей или как по другому решаются такие задачи

public class MaxLift {
public static void main(String[] args) {

    Man[] men = new Man[10];
    men[0] = new Man("0", 110);
    men[1] = new Man("1", 30);
    men[2] = new Man("2", 34);
    men[3] = new Man("3", 67);
    men[4] = new Man("4", 33);
    men[5] = new Man("5", 65);
    men[6] = new Man("6", 19);
    men[7] = new Man("7", 80);
    men[8] = new Man("8", 98);
    men[9] = new Man("9", 45);
    int liftMaxWeight = 200;

    TreeSet> set = new TreeSet<>();//add comparator
    for (int i = 0; i < men.length; i++) {
        List list  = new ArrayList<>();
        list.add()
    }

    //sout
}

private static class Man {
    String name;
    int weight;

    public Man(String name, int weight) {
        this.name = name;
        this.weight = weight;
    }
}


}
    

Ответы

Ответ 1

Так как в задании ничего не сказано про объём лифта, то решением является следующее.

Сортируем список людей начиная с самого малого веса, например:

20
25
27
30
40
50
60
75


И складываем подряд начиная с начала пока не получим максимальную массу.

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

Сложность алгоритма равна сложности сортировки. Но при желании можно ещё ускорить
не сортируя весь массив сразу, а сортируя только начало. Но это будет посложнее организовать,
так как придётся алгоритм сортировки писать вручную.


Ответ 2

Итак, ваш вопрос не как вычислить максимальное число людей в лифте, а "Хочу сначала
узнать все возможные комбинации и потом выводить максимальное. Но как узнать кобинации
этих людей".

Тогда можно просто перебирать все числа от 0 до 2N-1, где N - число людей. Дальше
каждое число в бинарном представлении - просто набор 0 и 1, соответствующих конкретным
людям, а все числа - все возможные варианты. Типа, для трех человек ABC:

0  000   никого :)
1  001   A
2  010   B
3  011   AB
4  100   С
5  101   AC
6  110   BC
7  111   ABC


Ответ 3

Чтобы найти сколько людей может в лифте поместиться, учитывая максимальный вес, можно
отсортировать веса людей и прибавлять от меньшего к большему весу до тех пор пока кумулятивный
вес меньше максимальной нагрузки лифта. На Питоне:

#!/usr/bin/env python
import itertools

weights = 110, 30, 34, 67, 33, 65, 19, 80, 98, 45
capacity = 200
for n, cumsum in enumerate(itertools.accumulate(sorted(weights))):
    if cumsum > capacity:  # no more
        print(n)
        break
else: # no break: all people can come in
    print(len(weights))


Ответ: 5 что совпадает с результатом более общего алгоритма для задачи о рюкзаке.



Weights:  Max weight: