Help with task using array. lazarus / 21-General ---------------------------------------------------------------------- Stycx · 2021-03-02 19:31 Please help me with this task I need for school. There is a line with those who want to ride at the lift with a load capacity of 500 kg. When the elevator door opens, customers step into the elevator in a row until it declares that the load capacity has been exceeded. Draw up a program stating which driver should disembark in order for the lift to reach the largest possible passenger mass. What will this mass be? The amount of people and their individual mass is determined by the user. Please help ---------------------------------------------------------------------- bytebites · 2021-03-02 19:34 Please show what you have done. ---------------------------------------------------------------------- Stycx · 2021-03-02 19:47 Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i program Arrays1i;var n,d,b,c:integer;  a:array[1..10000] of integer;  begin  write('How many people will use the lift? ');    readln(n);    b:=0;  for d:=1 to n do    begin    write(d,'. persons mass ');    readln(a[d]);    b:=b+a[d];    end;    if b<=500 then    writeln('Everyone can ride the lift!'); end.    I have no idea on how to get the part, where it choses from the array a person to leave behind to maximize the lifts maximum capacity, which is 500. Please note, that I have been using Lazarus for only like a month and it's my first programming language, so if there are wrong variable types or some other mistakes, please be sure to point them out          [Edited to add code tags: please read How to use the Forums.] ---------------------------------------------------------------------- Stycx · 2021-03-02 19:50 I forgot to mention, but the program must specify which person I threw out of the lift. ---------------------------------------------------------------------- winni · 2021-03-02 21:23 Hi! For better readability: Use the code tags for your code. And for the easier understanding of your code dont name the variables a,b,c but (here) mass, count and so on. And you dont want to compute 10.000 persons, because the lift might be full before. So one criterion is your magic "500" - kg I think. And the second criterion is the high bound of your array. If you try to write to a[10001] it will crash. So the updated code looks like that: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i program Arrays1i;var count,mass: integer;  a:array[1..10000] of integer;  full : boolean = false;  begin    writeln('How many people will use the lift? ');    mass:=0;    count := low(a);    while not full and (count <= high(a)) do    begin    write(count,'. persons mass ');    readln(a[count]);    mass:=mass+a[count];    full := mass> 500;    if full then writeln ('Person ',count, ' must leave') else        writeln ('Ok');    inc(count);    end;end.  Winni ---------------------------------------------------------------------- Stycx · 2021-03-02 22:12 Hello, Winni! I think some parts of your code work, but in the rules of the task the user must input how many people are standing at the line for the lift. I don't know if I will explain this right, but I will try. For example the user puts that 6 people are in the line waiting. The user needs to input their masses. I will write some for example. 1st 97kg, 2nd 83kg, 3rd 103kg, 4th 76kg, 5th 89kg and the 6th 98kg. The task requires, that I need to use the most weight in the lift that doesn't exceed 500kg. If I were to add the first 5 peoples mass it would be 448kg, but if I were to replace the 4th person with the 6th then the mass would be 470kg. And in this case the 4th person would be thrown out. If the mass of the 6 people would be under 500 then the lift would just go, but since the mass exceeds the 500kg, I need to choose those people, whos combined mass will be either 500kg or the closest to 500kg It's a really complicated task for me, and I don't know how to do this exactly. I understand, if you don't want to try to write it again with these requirements, but I am thankful for your first attemp. ---------------------------------------------------------------------- winni · 2021-03-02 22:33 Hi! Okay, I understood your mind game. But back to reality: You want to  tell Arnold Schwarzenegger to leave the lift, because only that little Hobbit in the back is allowed to enter??? Oh boy! And second: The official shown mass limit has a very big tolerance especially in lifts!! Anyway: If you got let's say 5 persons breaking the 500 kg limit, then you have to check all combinations with 4 persons that come nearest to the limit. You have to check 2+3+4+5 = 1+3+4+5 = 1+2+4+5= 1+2+3+5= 1+2+3+4= You see: this is a job for a loop and you allways drop one position. And for every position you have to compute 500 - sum[loop]. Winni ---------------------------------------------------------------------- AL · 2021-03-02 22:34 To find which person should leave you need something like this (not tested)  This will only remove one person Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i     program Arrays1i;    Const  MaxWeight = 500 ;     var count,mass,          MustLeave, Overweight, i : integer;          a   : array[1..10000] of integer;          full : boolean = false;      begin        writeln('How many people will use the lift? ');        mass:= 0;      count := low(a);        while not full and (count <= high(a)) do      begin         write(count,'. persons mass ');         readln(a[count]);         mass := mass + a[count];         full := mass > 500;         inc(count);        end;         if not full then         writeln ('Ok')        else        begin   // search which person should leave              OverWeight := Mass - MaxWeight ;         MustLeave := Count ; // assume the last entered will leave         For i := Count downto 1 do      // count down to keep priority         begin              if a[i] >= OverWeight then                          // make sure the person is heavy enough                 if a[i] > a[Mustleave] then MustLeave := i ;  // scan the array to find a lighter person           end; //for                                 writeln ('Person ',MustLeave, ' must leave')            end. ---------------------------------------------------------------------- dbannon · 2021-03-02 22:41 I am pretty sure Winni  (or anyone else) won't write it for you here Stycx, its a school project and you need to write it. But maybe we can give some hints that will help. I suspect Winni's hint about good variable names is a very important one, I sure would mark you down for using n, d, b and c. If the task is to get the most people into the lift without exceeding a particular weight, I reckon I would take the lightest people first. Has the topic of sorting been mentioned in recent lectures ? If the task is to get as close to the particular weight but still be under it, its a combination thing. And maybe then its trying 'random' combinations recording the combination that returns the highest. That might be a bit advanced (although I am sure you could do it if you tried) so I expect its the "most people" model.  Don't forget, some people can be quiet light ... People here (both light ones and heavy ones) will be very keen to comment on your code but you must write it ! So, show us what you can do. Davo ---------------------------------------------------------------------- speter · 2021-03-02 22:48 Stycx, I suggest having an array and then filling the array with random numbers, for example: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i const  max=10;var   people : array [1..max of integer;  a : byte;begin  randomize;  for a := 1 to 10 do    people[a] := 50 + random(76); // meaning people mass 50. .125 kg Then you need to work out - using those "people" - which selection gets you closest to 500. cheers S. ---------------------------------------------------------------------- 440bx · 2021-03-02 22:49 @dbannon posted while I was writing this and, the essence of what he stated is pretty much what I stated as well.  I'm not going to give you the code but, I will give you the solution. Before anything, it's important to underline that the solution is to maximize the amount of weight and _not_ the number of people.  That's important because, it is possible that a lower number of people come closer to the maximum weight but, that solution would not be acceptable to Mr. Spock.  Paraphrasing, the needs of multiple skinny ones outweigh the needs of one fat one.   (if you don't agree take it with a Vulcan.) For what you mentioned the solution is fairly simple.  Just sort the occupants by weight.  If the occupants exceed the maximum weight, usually simply removing the lightest occupant will do but, in some cases you may need to scan through the occupants from lesser weight to greater weight until you find the _one_ occupant that when removed makes the total weight acceptable while keeping it closest to the maximum allowed weight. Of course, there will be some cases where more than one occupant has to be removed.  That's when things get really interesting and where Mr. Spock might conclude the solution to be illogical since there can be cases where a greater number of occupants would weigh less than a lower number of occupants that maximize the weight but, either solution can be systematically found when the occupants are sorted by weight.  That would be a particularly nasty problem, morally and mathematically, if for instance, 2 people would come within a pound of the maximum and 5 people would also come within a pound of the maximum.  Your algorithm has to decide if 2 people get high or 5 people get high (because of the lift, of course.) HTH. ---------------------------------------------------------------------- Stycx · 2021-03-02 23:01 @440bx Okay, thank you for all the tips. I would have had pretty much the same idea that Winni had, that I would have needed to check the combinations of those people and their weight, and then just try to somehow extract the closest one to 500kg ---------------------------------------------------------------------- winni · 2021-03-02 23:13 Hi! Or the corona solution that I see on the job: A big sign in the lift: "Please use this lift single or only with your relatives" That is the way complicated math problems are solved today! Winni ---------------------------------------------------------------------- Stycx · 2021-03-02 23:16 Also I usually try to do these tasks myself, and I have done them myself with usually 0 problems, because I know, these things will come in handy in future codes, but this one just beat me with a stick. This was our second lesson trying to code using arrays, and the first one compared to this one was really easy, so after some hours of thinking about how I could have done this I pretty much gave up. Thank you @dbannon and @Winni for telling to use different variable names. I haven't really given a big thought about them, because our teacher doesn't really care, but I will try to remember this in the future. And thanks to @440bx and everyone else for the tips. Also true Winni, it seems our teacher has forgotten about the on going situation  I will try to put this together in the morning, because it's 1 am for me. Hopefully it goes well, because you have given me a different point of view on how to conquer this problem. This was my first time asking for help here, and I am glad that there is such a helpful community here! ---------------------------------------------------------------------- ASBzone · 2021-03-02 23:17 Quote from: Stycx on March 03, 2021, 12:01:53 amOkay, thank you for all the tips. I would have had pretty much the same idea that Winni had, that I would have needed to check the combinations of those people and their weight, and then just try to somehow extract the closest one to 500kg Lots of good suggestions so far. I would be inclined to go for the most (technically) inefficient solution of generating all the sums up to the total number of people, and then choosing the closest one below 500kg. So, if the number of people was 6, and the total sum of all 6 exceeded 500kg, then I would loop through and calculate the following: Sum of person 1 Sum of person 2 ... Sum of person 6 Sum of each combination of 2 persons (1,2; 2;3; 3,4; etc) ... Sum of each [/size]combination [/size]of 5 persons Then, get the closest one to 500kg without going over. That's a lot of iterations, but fairly straightforward to do. ---------------------------------------------------------------------- ASBzone · 2021-03-02 23:18 Quote from: winni on March 03, 2021, 12:13:26 am"Please use this lift single or only with your relatives" That is the way complicated math problems are solved today! LOL ---------------------------------------------------------------------- norm · 2021-03-02 23:36 Develop an algorithm to find the largest possible passenger mass ('largest'), and the person who should disembark ('disembark'). (a) Loop through the array ('a') while saving the mass of each rider as they enter the lift. (b) Keep a running total ('sum') of the mass of all the riders as they enter. (c) After the load limit is exceeded, save the running total and number of riders ('nriders') up to this point, including the rider that caused the limit to be exceeded. (d) Loop through the array with "for j = 1 to nriders do". If "sum - a[j]" is greater than "largest" then set "largest := sum - a[j]" and "disembark := j". "sum - a[j]" should not exceed the load limit. (e) Display results (Largest possible passenger mass := "largest" and "Rider No 'disembark' should disembark"). Good luck. ---------------------------------------------------------------------- Kays · 2021-03-02 23:43 Quote from: Stycx on March 02, 2021, 11:12:47 pm[…] The task requires, that I need to use the most weight in the lift that doesn't exceed 500kg. […]If you want to “cheat”, this kind of task is known as backpack problem (except that your “backpack” is an elevator and all “items” have a constant value, since you merely want to maximize the number of people). By the mere length of the English Wikipedia page you can infer it’s not a simple task. Now, obviously your class isn’t about finding the mathematically best and efficient solution, though, so ideally do just what winni already suggested: Quote from: winni on March 02, 2021, 11:33:46 pm[…] You have to check 2+3+4+5 = 1+3+4+5 = […]That’s the brute-force approach. From your code I can see you already know enough to achieve that. You know how to access array components and how to use for-loops. The difficult thing is maybe to generate all possible passenger combinations, to construct a power set. ---------------------------------------------------------------------- dseligo · 2021-03-03 00:41 My solution: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i program Arrays1i;const n=20;var d,b,c,i,best_mass,must_exit:integer;    a:array[1..500] of integer;begin  randomize;  for d:=1 to n do    a[d]:=1+random(150);   // calculate mass of first "d" people entering lift  b:=0;  d:=0;  while (d best_mass) then      begin        best_mass:=b-a[i];        must_exit:=i;      end;  end;   // print results  Write('Masses of people entered the lift:');  For i:=1 to d do    Write(' ',a[i]);  WriteLn;  WriteLn('Initial mass: ',b,' kg');   If b>500 then   begin  WriteLn('Person No. ',must_exit,' must exit lift.');    WriteLn('Riding mass: ',best_mass);  end;end. ---------------------------------------------------------------------- lucamar · 2021-03-03 01:57 Quote from: winni on March 03, 2021, 12:13:26 amA big sign in the lift: "Please use this lift single or only with your relatives" That shows a quite big logical problem if you're married but your spouse and relations are some other place. Unless all your other relations are dead, of course; then the second clause might apply ... ---------------------------------------------------------------------- avk · 2021-03-03 06:47 Quote from: Kays on March 03, 2021, 12:43:35 am... this kind of task is known as backpack problem (except that your “backpack” is an elevator and all “items” have a constant value, since you merely want to maximize the number of people). By the mere length of the English Wikipedia page you can infer it’s not a simple task. This task would be a knapsack problem if initially it was required to select a group of passengers that maximizes the mass of the elevator with a limited load capacity. Finding one among the already existing set of passengers, the exclusion of which maximizes the mass of the elevator so that the mass remains within the load capacity, is an O(n) problem and I believe @norm and @dseligo have already provided a solution. ---------------------------------------------------------------------- Zvoni · 2021-03-03 06:49 This reminds of the "solver"-AddIn in Excel. Maybe research an algorithm with that keyword ---------------------------------------------------------------------- Kays · 2021-03-03 09:51 Quote from: avk on March 03, 2021, 07:47:33 amThis task would be a knapsack problem if initially it was required to select a group of passengers that maximizes the mass of the elevator with a limited load capacity. […]Huh, you’re right. Stycx’s second post describing the problem didn’t really point it out, but the opening post said there’s a line. In a line it’s FCFS (first come, first serve): The passenger who boarded the elevator first will never be asked to leave [unless they weigh over 500 kg]. The backpack problem, though, doesn’t have a “line”, so it’s a different problem. Maybe you could model this as a BP problem: Assign the first passenger a “value” of 4, the second as 2, and the third and last passenger 1 [so 2n−i]. Would this help?