Recent

Author Topic: Help with task using array.  (Read 2071 times)

ASBzone

  • Hero Member
  • *****
  • Posts: 678
  • Automation leads to relaxation...
    • Free Console Utilities for Windows (and a few for Linux) from BrainWaveCC
Re: Help with task using array.
« Reply #15 on: March 03, 2021, 12:18:41 am »
"Please use this lift single or only with your relatives"

That is the way complicated math problems are solved today!

LOL
-ASB: https://www.BrainWaveCC.com/

Lazarus v2.2.7-ada7a90186 / FPC v3.2.3-706-gaadb53e72c
(Windows 64-bit install w/Win32 and Linux/Arm cross-compiles via FpcUpDeluxe on both instances)

My Systems: Windows 10/11 Pro x64 (Current)

norm

  • New Member
  • *
  • Posts: 13
Re: Help with task using array.
« Reply #16 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.
 
« Last Edit: March 03, 2021, 01:31:25 pm by norm »

Kays

  • Hero Member
  • *****
  • Posts: 569
  • Whasup!?
    • KaiBurghardt.de
Re: Help with task using array.
« Reply #17 on: March 03, 2021, 12:43:35 am »
[…] 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:
[…]
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.
Yours Sincerely
Kai Burghardt

dseligo

  • Hero Member
  • *****
  • Posts: 1181
Re: Help with task using array.
« Reply #18 on: March 03, 2021, 01:41:59 am »
My solution:
Code: Pascal  [Select][+][-]
  1. program Arrays1i;
  2. const n=20;
  3. var d,b,c,i,best_mass,must_exit:integer;
  4.     a:array[1..500] of integer;
  5. begin
  6.   randomize;
  7.   for d:=1 to n do
  8.     a[d]:=1+random(150);
  9.  
  10.   // calculate mass of first "d" people entering lift
  11.   b:=0;
  12.   d:=0;
  13.   while (d<n) and (b<500) do
  14.   begin
  15.     inc(d);
  16.     b:=b+a[d];
  17.   end;
  18.  
  19.   if b<=500 then
  20.     WriteLn('Nobody has to exit lift.')
  21.   else
  22.   begin
  23.     // index of last person entered in lift is in variable d
  24.     // we test from 1 to d which person should leave
  25.     best_mass:=0;
  26.     for i:=1 to d do
  27.       if (b-a[i] < 500) and (b-a[i] > best_mass) then
  28.       begin
  29.         best_mass:=b-a[i];
  30.         must_exit:=i;
  31.       end;
  32.   end;
  33.  
  34.   // print results
  35.   Write('Masses of people entered the lift:');
  36.   For i:=1 to d do
  37.     Write(' ',a[i]);
  38.   WriteLn;
  39.   WriteLn('Initial mass: ',b,' kg');
  40.  
  41.   If b>500 then
  42.   begin
  43.     WriteLn('Person No. ',must_exit,' must exit lift.');
  44.     WriteLn('Riding mass: ',best_mass);
  45.   end;
  46. end.

lucamar

  • Hero Member
  • *****
  • Posts: 4219
Re: Help with task using array.
« Reply #19 on: March 03, 2021, 02:57:49 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
Turbo Pascal 3 CP/M - Amstrad PCW 8256 (512 KB !!!) :P
Lazarus/FPC 2.0.8/3.0.4 & 2.0.12/3.2.0 - 32/64 bits on:
(K|L|X)Ubuntu 12..18, Windows XP, 7, 10 and various DOSes.

avk

  • Hero Member
  • *****
  • Posts: 752
Re: Help with task using array.
« Reply #20 on: March 03, 2021, 07:47:33 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

  • Hero Member
  • *****
  • Posts: 2300
Re: Help with task using array.
« Reply #21 on: March 03, 2021, 07:49:18 am »
This reminds of the "solver"-AddIn in Excel.
Maybe research an algorithm with that keyword
One System to rule them all, One Code to find them,
One IDE to bring them all, and to the Framework bind them,
in the Land of Redmond, where the Windows lie
---------------------------------------------------------------------
Code is like a joke: If you have to explain it, it's bad

Kays

  • Hero Member
  • *****
  • Posts: 569
  • Whasup!?
    • KaiBurghardt.de
Re: Help with task using array.
« Reply #22 on: March 03, 2021, 10:51:53 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 2n−i]. Would this help?
« Last Edit: March 03, 2021, 11:01:51 am by Kays »
Yours Sincerely
Kai Burghardt

 

TinyPortal © 2005-2018