1

Задача похожа на предыдущий вопрос, только здесь цель другая, изначально задача была неправильно понята. В предыдущей задаче надо было вычислить максимальное количество людей вместимых в лифт, а в этом надо максимально нагрузить лифт. Изначально задача была не правильно понята Дано список людей с именем и весом, максимальный вес который выдержит лифт. Вычислить максимальный вес которое может поместиться и вывести их список, какие люди поместятся чтобы максимально нагрузить лифт.

Не понимаю как определить комбинацию людей которые могут быть. Ведь может быть разные комбинации, 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;
}
 }
 }
8
  • 4
    Возможный дубликат вопроса: Вычисление максимального количества людей в лифте
    – Kromster
    31 мар 2018 в 17:48
  • 2
    Вам же уже ответили на оба вопроса!
    – Harry
    31 мар 2018 в 17:51
  • 3
    А вот это уже классическая задача о рюкзаке; Здесь полный перебор — одно из валидных (хотя не самых эффективных) решений... ЗЫ: стоило бы вынести отдельным абзацем с заголовком, в чём отличие от предыдущего вопроса...
    – Fat-Zer
    31 мар 2018 в 17:53
  • 1
    Не успел предупредить, хорошо бы пояснить в вопросе почему новый создали, у нас на SO люди любят минусовать за разное и блокировки кидать. Как-то так написать, что тот вопрос был поставлен некорректно и оказалось что задача в другом. Я то понимаю почему создали, а кто новый заходит не в теме ситуации. 31 мар 2018 в 18:01
  • 1
    @ДмитрийПолянин Да классическое ДП. Задача разобрана множество раз.
    – Harry
    31 мар 2018 в 18:09

2 ответа 2

3

Вычисление максимального возможного веса при заполнении лифта людьми с указанными весами, можно выполнить используя упрощённое решение для задачи о рюкзаке 0-1 O(n W) по времени O(W) в памяти решение (n - количество людей, W - грузоподъёмность), на Питоне:

#!/usr/bin/env python3
"""Find max weight given people weights, elevator capacity."""

weights = 110, 30, 34, 67, 33, 65, 19, 80, 98, 45
capacity = 200

# m[c] — max possible weight using items seen so far under *c* capacity
m = [0] * (capacity + 1)
prev = m[:]  # previous value (without the current item)
for w in weights:
    for c in range(capacity + 1):
        m[c] = prev[c] if w > c else max(prev[c], prev[c-w] + w)
    prev, m = m, prev
print('Max weight:', prev[-1])

Вывод: Max weight: 200 (можно заполнить до максимальной нагрузки). Что совпадает с ответом, получаемым адаптацией более общего решения из вопроса Задача о рюкзаке (ранце) python.

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

def max_weight(weights, capacity):
    m = [0] * (capacity + 1)
    prev = m[:]  # previous value (without the current item)
    for w in weights:
        for c in range(capacity + 1):
            m[c] = prev[c] if w > c else max(prev[c], prev[c-w] + w)
        prev, m = m, prev
    return prev[-1]

@document["mybutton"].bind("click") 
def on_click(event=None):
    capacity = int(document["capacity"].value)
    weights = json.loads(document["json"].value)
    print(f"{capacity}, {weights} -> {max_weight(weights, capacity)}")
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>

9
  • В задаче нужно вычислить список людей 1 апр 2018 в 13:06
  • 1- нажмите на ссылку в ответе, где представлено более общее решение -- оно возвращает кто был выбран 2- заголовок вопроса явно говорит: найти максимальный вес, а не список людей.
    – jfs
    1 апр 2018 в 13:09
  • Да, прошу прощения, заголовок не правильный( 1 апр 2018 в 13:10
  • @AlexanderBelov по ссылкам в ответе есть пошаговое словесное описание алгоритма в другом моём ответе и псевдо-код на Википедия страничке (из которого Питон-код был написан). Данный алгоритм на Java нормально должен выражаться (несколько простых циклов с использованием массивов).
    – jfs
    1 апр 2018 в 17:13
  • Я решаю с перерывом, все еще нет времени полностью сесть, не подумайте что до сих пор решаю, хотя признаю что задача очень сложная 2 апр 2018 в 6:51
2

Я вижу такое решение:

Сначала отсортировать массив людей начиная от больших к меньшим.

Перебирать методом который в прошлом вопросе сказал Harry, сначала беря 00000 потом 10000 01000 11000 00100 10100 и так далее.

Суммирование начинаем слева направо, если сумма превысила предел то прекращаем перебор по всей ветке, со всеми числами далее.

То есть если есть вариант [abcdef]ghij и сумма [abcdef] уже больше предела, то остаток [ghij] уже перебирать смысла нету, и эту часть пропускаем.

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

2
  • То есть если есть вариант [abcdefghij и сумма [abcdef] уже больше предела, то остаток [ghij] уже перебирать смысла нету, и эту часть пропускаем. Не понимаю, ведь если сумма [abcdef] больше можно же попробовать вместо f прибавить g, потому что g меньше f, соответственно может не привысить 1 апр 2018 в 5:51
  • @AlexanderBelov это да, я имею ввиду что варианты с [abcdef]xxxx где разные xxxx уже не надо подбирать, а [fbcdef] фиксированы. 1 апр 2018 в 8:23

Ваш ответ

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

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