The task is similar to the previous question , only here the goal is different, initially the task was misunderstood. In the previous task, it was necessary to calculate the maximum number of people accommodated in the elevator, and in this we should maximally load the elevator. Initially, the task was not properly understood. A list of people with a name and weight is given, the maximum weight that the lift can withstand. Calculate the maximum weight that can fit and display a list of what people fit to load the elevator as much as possible.

I do not understand how to determine the combination of people that may be. After all, there may be different combinations, 1, 2, 3 or 1, 2, 4, or 1, 3, 5, 6. I want to first find out all the possible combinations of capable people and then display the maximum. But how to find out the combinations of these people or how such problems are solved differently.

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; } } }
  • four
    Possible duplicate question: Calculate the maximum number of people in the elevator - Kromster
  • 2
    You have already answered both questions! - Harry
  • 3
    But this is already a classic backpack problem ; Here a complete bust is one of the valid (though not the most effective) solutions ... Shl: it would be worthwhile to take out a separate paragraph with a heading, what is the difference from the previous question ... - Fat-Zer
  • one
    I did not have time to warn you, it would be good to explain in the question why the new one was created, at SO people like to minus for different things and blocking to throw. Somehow to write that the question was posed incorrectly and it turned out that the task was different. I understand why they created it, and who created the new is not in the subject of the situation. - Dmitry Polyanin
  • one
    @DmitryPolyanin Yes, the classic DP. The task is parsed many times. - Harry

2 answers 2

Calculation of the maximum possible weight when filling the elevator with people with the specified weights can be performed using a simplified solution for the 0-1 O(n W) backpack problem by O(n W) time in the memory solution ( n is the number of people, W is the load capacity), Python:

 #!/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[cw] + w) prev, m = m, prev print('Max weight:', prev[-1])

Output: Max weight: 200 (can fill up to maximum load). That coincides with the answer obtained by adapting a more general solution from the question The python knapsack problem (knapsack) .

 <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[cw] + 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>

  • In the task you need to calculate the list of people - Alexander Belov
  • 1- click on the link in the answer where a more general solution is presented - it returns who was selected 2- the title of the question clearly says: find the maximum weight , not a list of people. - jfs
  • Yes, I apologize, the title is not correct ( - Alexander Belov
  • @AlexanderBelov the links in the answer are a step-by-step verbal description of the algorithm in my other answer and a pseudo-code on the Wikipedia page (from which the Python-code was written). This Java algorithm should normally be expressed (several simple loops using arrays). - jfs
  • I decide with a break, there is still no time to sit down completely, do not think that I am still solving, although I admit that the task is very difficult - Alexander Belov

I see this solution:

First, sort the array of people ranging from large to smaller.

To go through the method that told Harry in the last question , first taking 00000 then 10000 01000 11000 00100 10100 and so on.

We start the summation from left to right, if the amount exceeds the limit, then we stop searching through the entire branch, with all the numbers further.

That is, if there is an option [abcdef] ghij and the sum of [abcdef] is already greater than the limit, then the remainder [ghij] already has no sense in sorting, and skip this part.

Sorting from larger to smaller will allow you to discard the maximum number of variants, since an extra ending consisting of the smallest numbers will be maximum in length, and this means that the largest number of variants will be discarded, compared to any other sort.

  • That is, if there is a variant [abcdefghij and the sum [abcdef] is already greater than the limit, then the remainder [ghij] already has no sense in sorting, and skip this part. I don’t understand, because if the sum [abcdef] is more, you can try adding g to f instead of f, because g is less than f, respectively, it may not increase - Alexander Belov
  • @AlexanderBelov is yes, I mean that the options with [abcdef] xxxx where different xxxx no longer need to be selected, and [fbcdef] are fixed. - Dmitry Polyanin