5

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

Не понимаю, как определить комбинацию людей которые могут быть. Ведь может быть разные комбинации, 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<List<Man>> set = new TreeSet<>();//add comparator
    for (int i = 0; i < men.length; i++) {
        List<Man> 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

3 ответа 3

7

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

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

20
25
27
30
40
50
60
75

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

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

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

3
  • Прошу прощения, не правильно понял саму задачу и соответственно описал не правильно. Если знаете помогите. тут по сложнее задача стоит) 31 мар 2018 в 17:23
  • @AlexanderBelov В таких ситуациях лучше оформить отдельным вопросом, а в этом пометить решением то что является им. Так как авторы ответов проделали работу и хорошо бы её оценить, а не сбрасывать апдейтом вопроса. 31 мар 2018 в 17:34
  • Да, вы правы, я так и подумал 31 мар 2018 в 17:36
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
10
  • 1
    Добавлю, что если всё же решать саму задачу, то полный перебор тут абсолютно излишен.
    – Fat-Zer
    31 мар 2018 в 16:13
  • @Fat-Zer Именно. Потому я и сделал оговорку вначале...
    – Harry
    31 мар 2018 в 16:16
  • @harry не знаю как можно без перебора, подскажите пожалуйста 31 мар 2018 в 16:23
  • @Fat-Zer подскажите, как можно решать такую задачу без перебора? 31 мар 2018 в 16:40
  • 2
    @AlexanderBelov, подсказка: если в лифт не влезают N самых лёгких людей, то если поменять одного из них на кого-то потяжелее тяжёлого, то они всё равно не влезут...
    – Fat-Zer
    31 мар 2018 в 16:50
2

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

#!/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 что совпадает с результатом более общего алгоритма для задачи о рюкзаке.

<script src="https://cdn.rawgit.com/brython-dev/brython/3.4.0/www/src/brython.js"></script><script src="https://cdn.rawgit.com/brython-dev/brython/3.4.0/www/src/brython_stdlib.js"></script><body onload="brython()"><script type="text/python">
import itertools
import json
from browser import document

def max_nitems(weights, capacity):
    for n, cumsum in enumerate(itertools.accumulate(sorted(weights))):
        if cumsum > capacity:  # no more
            return n
    return len(weights) # all people can come in

@document["mybutton"].bind("click") 
def on_click(event=None):
    capacity = int(document["capacity"].value)
    weights = json.loads(document["json"].value)
    nitems = max_nitems(weights, capacity)
    print(f"{capacity}, {weights} -> {nitems}")
on_click('dummy on start')
</script><label for="json">Weights: </label><input id="json" value="[110, 30, 34, 67, 33, 65, 19, 80, 98, 45]"> <label for="capacity">Max&nbsp;weight: <input id="capacity" value="200"> <button id="mybutton">Запустить</button></body>

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.