Knapsack problem/Continuous: Difference between revisions
Content added Content deleted
m (→{{header|REXX}}: simplified a DO loop assignments, changed some indentations.) |
Walterpachl (talk | contribs) (add PL/I and REXX (version 2)) |
||
Line 613: | Line 613: | ||
items(9) = Item("sausage", 5.9, 98.0) |
items(9) = Item("sausage", 5.9, 98.0) |
||
! sort items in |
! sort items in descending order of their value per unit weight |
||
do i = 2, size(items) |
do i = 2, size(items) |
||
j = i - 1 |
j = i - 1 |
||
Line 1,334: | Line 1,334: | ||
welt 3.50 63.38 |
welt 3.50 63.38 |
||
</pre> |
</pre> |
||
=={{header|PL/I}}== |
|||
<lang pli>*process source xref attributes; |
|||
KNAPSACK_CONTINUOUS: Proc Options(main); |
|||
/*-------------------------------------------------------------------- |
|||
* 19.09.2014 Walter Pachl translated from FORTRAN |
|||
*-------------------------------------------------------------------*/ |
|||
Dcl (divide,float,hbound,repeat) Builtin; |
|||
Dcl SYSPRINT Print; |
|||
Dcl maxweight Dec Fixed(15,3); |
|||
maxweight = 15.0; |
|||
Dcl (total_weight,total_value) Dec Fixed(15,3) Init(0); |
|||
Dcl vpu Dec Float(15); |
|||
Dcl (i,j) Bin Fixed(31); |
|||
Dcl 1 item(9), |
|||
2 name Char(7), |
|||
2 weight Dec Fixed(15,3), |
|||
2 value Dec Fixed(15,3); |
|||
Dcl temp Like item; |
|||
Call init_item(1,'beef', 3.8, 36.0); |
|||
Call init_item(2,'pork', 5.4, 43.0); |
|||
Call init_item(3,'ham', 3.6, 90.0); |
|||
Call init_item(4,'greaves', 2.4, 45.0); |
|||
Call init_item(5,'flitch', 4.0, 30.0); |
|||
Call init_item(6,'brawn', 2.5, 56.0); |
|||
Call init_item(7,'welt', 3.7, 67.0); |
|||
Call init_item(8,'salami', 3.0, 95.0); |
|||
Call init_item(9,'sausage', 5.9, 98.0); |
|||
/* sort item in descending order of their value per unit weight */ |
|||
do i = 2 To hbound(item); |
|||
j = i - 1; |
|||
temp = item(i); |
|||
do while(j>=1&item(j).value/item(j).weight<temp.value/temp.weight); |
|||
item(j+1) = item(j); |
|||
j = j - 1; |
|||
end; |
|||
item(j+1) = temp; |
|||
end; |
|||
Do i=1 To hbound(item); |
|||
Put Edit(i,item(i))(Skip,f(2),x(2),a(7),2(f(8,3))); |
|||
End; |
|||
i = 0; |
|||
Put Skip; |
|||
Put Edit('Item Weight Value')(Skip,a); |
|||
do i=1 By 1 while(i < hbound(item) & total_weight < maxweight); |
|||
if total_weight+item(i).weight < maxweight then Do; |
|||
total_weight = total_weight + item(i).weight; |
|||
total_value = total_value + item(i).value; |
|||
Put Edit(item(i))(Skip,a(7),2(f(8,3))); |
|||
End; |
|||
Else Do; |
|||
vpu=divide(item(i).value,item(i).weight,15,8); |
|||
item(i).weight=maxweight-total_weight; |
|||
item(i).value=float(item(i).weight)*vpu; |
|||
total_value = total_value + item(i).value; |
|||
total_weight = total_weight + item(i).weight; |
|||
Put Edit(item(i).name, item(i).weight, item(i).value) |
|||
(Skip,a(7),2(f(8,3))); |
|||
Leave Loop; |
|||
end; |
|||
end; |
|||
Put Edit(repeat('-',22))(Skip,a); |
|||
Put Edit('total',total_weight, total_value)(Skip,a(6),f(9,3),f(8,3)); |
|||
init_item: Proc(i,name,weight,value); |
|||
Dcl i Bin Fixed(31); |
|||
Dcl name Char(*); |
|||
Dcl (weight,value) Dec Fixed(15,3); |
|||
item(i).name = name; |
|||
item(i).weight = weight; |
|||
item(i).value = value; |
|||
End; |
|||
End;</lang> |
|||
{{out}} |
|||
<pre> |
|||
1 salami 3.000 95.000 |
|||
2 ham 3.600 90.000 |
|||
3 brawn 2.500 56.000 |
|||
4 greaves 2.400 45.000 |
|||
5 welt 3.700 67.000 |
|||
6 sausage 5.900 98.000 |
|||
7 beef 3.800 36.000 |
|||
8 pork 5.400 43.000 |
|||
9 flitch 4.000 30.000 |
|||
Item Weight Value |
|||
salami 3.000 95.000 |
|||
ham 3.600 90.000 |
|||
brawn 2.500 56.000 |
|||
greaves 2.400 45.000 |
|||
welt 3.500 63.378 |
|||
----------------------- |
|||
total 15.000 349.378</pre> |
|||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
Line 1,644: | Line 1,743: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
===version 1=== |
|||
Any resemblence to the Fortran code is 120% coincidental. |
Any resemblence to the Fortran code is 120% coincidental. |
||
<lang rexx>/*REXX program solves the burglar's knapsack (continuous) problem. */ |
<lang rexx>/*REXX program solves the burglar's knapsack (continuous) problem. */ |
||
Line 1,736: | Line 1,836: | ||
total value─── 349.38 |
total value─── 349.38 |
||
</pre> |
</pre> |
||
===version2=== |
|||
<lang rexx> /*-------------------------------------------------------------------- |
|||
* 19.09.2014 Walter Pachl translated from FORTRAN |
|||
*-------------------------------------------------------------------*/ |
|||
maxweight = 15.0 |
|||
input.0=0 |
|||
Call init_input 'beef', 3.8, 36.0 |
|||
Call init_input 'pork', 5.4, 43.0 |
|||
Call init_input 'ham', 3.6, 90.0 |
|||
Call init_input 'greaves', 2.4, 45.0 |
|||
Call init_input 'flitch', 4.0, 30.0 |
|||
Call init_input 'brawn', 2.5, 56.0 |
|||
Call init_input 'welt', 3.7, 67.0 |
|||
Call init_input 'salami', 3.0, 95.0 |
|||
Call init_input 'sausage', 5.9, 98.0 |
|||
/* sort the items by descending value per unit of weight */ |
|||
Do i = 1 to input.0 |
|||
Parse Var input.i name '*' weight '*' value |
|||
vpu=value/weight; |
|||
If i=1 Then Do |
|||
item.0=1 |
|||
item.1=input.1 |
|||
vpu.1=vpu |
|||
End |
|||
Else Do |
|||
Do ii=1 To item.0 |
|||
If vpu.ii<vpu Then |
|||
Leave |
|||
End |
|||
Do jj=item.0 To ii By -1 |
|||
jj1=jj+1 |
|||
item.jj1=item.jj |
|||
vpu.jj1=vpu.jj |
|||
End |
|||
item.ii=input.i |
|||
vpu.ii=vpu |
|||
item.0=item.0+1 |
|||
End |
|||
End |
|||
Say '# vpu name weight value' |
|||
Do i=1 To item.0 |
|||
Parse Var item.i name '*' weight '*' value |
|||
Say i format(vpu.i,2,3) left(name,7) format(weight,2,3) format(value,3,3) |
|||
End |
|||
total_weight=0 |
|||
total_value =0 |
|||
Say ' ' |
|||
Say 'Item Weight Value' |
|||
Do i=1 To item.0 |
|||
Parse Var item.i name '*' weight '*' value |
|||
if total_weight+weight < maxweight then Do |
|||
total_weight = total_weight + weight |
|||
total_value = total_value + value |
|||
Say left(name,7) format(weight,3,3) format(value,3,3) |
|||
End |
|||
Else Do |
|||
weight=maxweight-total_weight |
|||
value=weight*vpu.i |
|||
total_value = total_value + value |
|||
total_weight = maxweight |
|||
Say left(name,7) format(weight,3,3) format(value,3,3) |
|||
Leave |
|||
End |
|||
End |
|||
Say copies('-',23) |
|||
Say 'total ' format(total_weight,4,3) format(total_value,3,3) |
|||
Exit |
|||
init_input: Procedure Expose input. |
|||
Parse Arg name,weight,value |
|||
i=input.0+1 |
|||
input.i=name'*'weight'*'value |
|||
input.0=i |
|||
Return</lang> |
|||
{{out}} |
|||
<pre># vpu name weight value |
|||
1 31.667 salami 3.000 95.000 |
|||
2 25.000 ham 3.600 90.000 |
|||
3 22.400 brawn 2.500 56.000 |
|||
4 18.750 greaves 2.400 45.000 |
|||
5 18.108 welt 3.700 67.000 |
|||
6 16.610 sausage 5.900 98.000 |
|||
7 9.474 beef 3.800 36.000 |
|||
8 7.963 pork 5.400 43.000 |
|||
9 7.500 flitch 4.000 30.000 |
|||
Item Weight Value |
|||
salami 3.000 95.000 |
|||
ham 3.600 90.000 |
|||
brawn 2.500 56.000 |
|||
greaves 2.400 45.000 |
|||
welt 3.500 63.378 |
|||
----------------------- |
|||
total 15.000 349.378</pre> |
|||
=={{header|Ruby}}== |
=={{header|Ruby}}== |