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

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

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