Print Page - Help with task using array.

Programming => General => Topic started by: Stycx on March 02, 2021, 08:31:58 pm

Title: Help with task using array.
Post by: Stycx on March 02, 2021, 08:31:58 pm

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

Title: Re: Help with task using array.
Post by: bytebites on March 02, 2021, 08:34:52 pm

Please show what you have done.

Title: Re: Help with task using array.
Post by: Stycx on March 02, 2021, 08:47:35 pm

Code: Pascal [Select][+]

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 (https://wiki.lazarus.freepascal.org/Forum).]

Title: Re: Help with task using array.
Post by: Stycx on March 02, 2021, 08:50:25 pm

I forgot to mention, but the program must specify which person I threw out of the lift.

Title: Re: Help with task using array.
Post by: winni on March 02, 2021, 10:23:06 pm

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

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

Title: Re: Help with task using array.
Post by: Stycx on March 02, 2021, 11:12:47 pm

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.

Title: Re: Help with task using array.
Post by: winni on March 02, 2021, 11:33:46 pm

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

Title: Re: Help with task using array.
Post by: AL on March 02, 2021, 11:34:46 pm

To find which person should leave you need something like this (not tested)
This will only remove one person

Code: Pascal [Select][+]

    
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.
     
 
 
 

Title: Re: Help with task using array.
Post by: dbannon on March 02, 2021, 11:41:26 pm

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

Title: Re: Help with task using array.
Post by: speter on March 02, 2021, 11:48:14 pm

Stycx,

I suggest having an array and then filling the array with random numbers, for example:

Code: Pascal [Select][+]

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.

Title: Re: Help with task using array.
Post by: 440bx on March 02, 2021, 11:49:59 pm

@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.

Title: Re: Help with task using array.
Post by: Stycx on March 03, 2021, 12:01:53 am

@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

Title: Re: Help with task using array.
Post by: winni on March 03, 2021, 12:13:26 am

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

Title: Re: Help with task using array.
Post by: Stycx on March 03, 2021, 12:16:18 am

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 :o

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!

Title: Re: Help with task using array.
Post by: ASBzone on March 03, 2021, 12:17:49 am

Quote from: Stycx on March 03, 2021, 12:01:53 am

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

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.

Title: Re: Help with task using array.
Post by: ASBzone on March 03, 2021, 12:18:41 am

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

Title: Re: Help with task using array.
Post by: norm on March 03, 2021, 12:36:55 am

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.

Title: Re: Help with task using array.
Post by: Kays on March 03, 2021, 12:43:35 am

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 (https://en.wikipedia.org/wiki/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 (https://en.wikipedia.org/wiki/Power_set).

Title: Re: Help with task using array.
Post by: dseligo on March 03, 2021, 01:41:59 am

My solution:

Code: Pascal [Select][+]

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<n) and (b<500) do
  begin
    inc(d);
    b:=b+a[d];
  end;
 
  if b<=500 then
    WriteLn('Nobody has to exit lift.')
  else
  begin
    // index of last person entered in lift is in variable d
    // we test from 1 to d which person should leave
    best_mass:=0;
    for i:=1 to d do
      if (b-a[i] < 500) and (b-a[i] > 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.

Title: Re: Help with task using array.
Post by: lucamar on March 03, 2021, 02:57:49 am

Quote from: winni on March 03, 2021, 12:13:26 am

A 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 ... :D

Title: Re: Help with task using array.
Post by: avk on March 03, 2021, 07:47:33 am

Quote from: Kays on March 03, 2021, 12:43:35 am

... this kind of task is known as backpack problem (https://en.wikipedia.org/wiki/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.

Title: Re: Help with task using array.
Post by: Zvoni on March 03, 2021, 07:49:18 am

This reminds of the "solver"-AddIn in Excel.
Maybe research an algorithm with that keyword

Title: Re: Help with task using array.
Post by: Kays on March 03, 2021, 10:51:53 am

Quote from: avk on March 03, 2021, 07:47:33 am

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. […]

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 2ⁿ⁻ⁱ]. Would this help?}