Recent

Author Topic: GREEDY ALGORITHM in Pascal  (Read 15326 times)

typo

  • Hero Member
  • *****
  • Posts: 3051
Re: GREEDY ALGORITHM in Pascal
« Reply #15 on: April 17, 2014, 11:43:38 am »
0/1 knapsack problem.

joydivision

  • Newbie
  • Posts: 6
Re: GREEDY ALGORITHM in Pascal
« Reply #16 on: April 17, 2014, 09:53:04 pm »
I would select the box with the highest y and take as much as he can (i.e. less then m).
Then select box with the second highest y and take as much as he can (m minus what he already have).
And so on.


Program Zadatak63;
Var weight : Array[1..10000] of Integer;
Var value : Array[1..10000] of Integer;
Var Noviweight : Array[1..10000] of Integer;
Var Novivalue : Array[1..10000] of Integer;
Var n : Integer;
Var i : Integer;
Var j : Integer;
Var val : Int64;
Var wei : Integer;
Var temp : Integer;
Begin
Write('N: ');
Readln(n);
For i := 1 to n do
      Begin
      Readln(weight);
      Readln(value);
      End;

Readln(wei);

For i := 2 to n-1 do
Begin
Noviweight := weight;
Novivalue := value;
   For j := i-1 downto 1 do
    Begin
    if (value[j] <= Novivalue) then
        Begin
         value[j+1] := value[j];
         weight[j+1] := weight[j];
        End;
   End;
   value[j+1] := Novivalue;
   weight[j+1] := Noviweight;
End;
wei := 0;
For i := 1 to n do
   Begin
    if (i <> 0) then
        Begin
    if (wei >= weight) then
        Begin
         temp := wei;
         wei := temp + value * weight;
        End;
   
    if (wei < weight) then
         Begin
         temp := val;
         val := temp + value * wei;
         wei := 0;
         End;
         End;
   End;

Write('value:', val);

End.


Is there any way to change the code smarter?
Please help.
This was so difficult!  %)

Blaazen

  • Hero Member
  • *****
  • Posts: 3237
  • POKE 54296,15
    • Eye-Candy Controls
Re: GREEDY ALGORITHM in Pascal
« Reply #17 on: April 17, 2014, 10:11:50 pm »
Can you edit your post, I mean close the code to tags:
Code: [Select]
[code] because forum ate all
Code: [Select]
[i] indexes and interpreted them as an italic font style.
Thanks.

At the beginning, I recommend to use dynamic array, it will save a lot of memory.
Code: [Select]
Var weight : Array of Integer;
Var value : Array of Integer;
...
Write('N: ');
Readln(n);
setlength(weight, n);
setlength(value, n);

But you will have to index from zero.
Lazarus 2.3.0 (rev main-2_3-2863...) FPC 3.3.1 x86_64-linux-qt Chakra, Qt 4.8.7/5.13.2, Plasma 5.17.3
Lazarus 1.8.2 r57369 FPC 3.0.4 i386-win32-win32/win64 Wine 3.21

Try Eye-Candy Controls: https://sourceforge.net/projects/eccontrols/files/

typo

  • Hero Member
  • *****
  • Posts: 3051
Re: GREEDY ALGORITHM in Pascal
« Reply #18 on: April 18, 2014, 12:44:37 am »
Maybe you could try something like this:

Code: [Select]
type
  TPiece = record
    Name :string[10];    // orange, apple, etc
    Weight,
    PricePerKg :integer;
  end;
var
  Pieces :array of TPiece;
begin
  SetLength(Pieces, Length(Pieces) + 1);
end;                                     
« Last Edit: April 18, 2014, 12:55:03 am by typo »

joydivision

  • Newbie
  • Posts: 6
Re: GREEDY ALGORITHM in Pascal
« Reply #19 on: May 08, 2014, 01:38:23 pm »
Can you edit your post, I mean close the code to tags:
Code: [Select]
[code] because forum ate all
Code: [Select]
[i] indexes and interpreted them as an italic font style.
Thanks.

At the beginning, I recommend to use dynamic array, it will save a lot of memory.
Code: [Select]
Var weight : Array of Integer;
Var value : Array of Integer;
...
Write('N: ');
Readln(n);
setlength(weight, n);
setlength(value, n);

But you will have to index from zero.

Code: [Select]

Program thief;
Var weight : Array[1..10000] of Integer;
Var value : Array[1..10000] of Integer;
Var Noviweight : Array[1..10000] of Integer;
Var Novivalue : Array[1..10000] of Integer;
Var n : Integer;
Var i : Integer;
Var j : Integer;
Var val : Int64;
Var wei : Integer;
Var temp : Integer;
Begin
Write('N: ');
Readln(n);
For i := 1 to n do
      Begin
      Readln(weight[i]);
      Readln(value[i]);
      End;

Readln(wei);

For i := 2 to n-1 do
Begin
Noviweight[i] := weight[i];
Novivalue[i] := value[i];
   For j := i-1 downto 1 do
    Begin
    if (value[j] <= Novivalue[i]) then
        Begin
         value[j+1] := value[j];
         weight[j+1] := weight[j];
        End;
End;
   value[j+1] := Novivalue[i];
   weight[j+1] := Noviweight[i];
End;

For i := 1 to n do
   Begin
    if (i <> 0) then
        Begin
    if (wei >= weight[i]) then
        Begin
         temp := wei;
         wei := temp + value[i] * weight[i];
        End;
   
    if (wei < weight[i]) then
         Begin
         temp := val;
         val := temp + value[i] * wei;
         wei := 0;
         End;
         End;
   End;

Write('value:', val);

End.

[code]


Could you somehow incorporate one boolean funct. and one procedure in this so it actually shows the result,because it's  still not working...

kenpem

  • New Member
  • *
  • Posts: 22
Re: GREEDY ALGORITHM in Pascal
« Reply #20 on: May 08, 2014, 06:47:22 pm »
This is starting to feel a lot like somebody's homework project...  8-)

Leledumbo

  • Hero Member
  • *****
  • Posts: 8746
  • Programming + Glam Metal + Tae Kwon Do = Me
Re: GREEDY ALGORITHM in Pascal
« Reply #21 on: May 09, 2014, 02:14:32 am »
This is starting to feel a lot like somebody's homework project...  8-)
As usual, just give hints, not code. Starting from the least obvious hint. If he can't do it until the most obvious one, then your curiosity might be right ;)

 

TinyPortal © 2005-2018