65 lines
2.1 KiB
Fortran
65 lines
2.1 KiB
Fortran
Program Knapsack01
|
|
! Translation of Pascal version on Rosetta Code.
|
|
implicit none
|
|
integer, parameter :: NUM_ITEMS = 22
|
|
integer, parameter :: MAX_WEIGHT = 400
|
|
type :: TItem
|
|
character(len=20) :: Name
|
|
integer :: Weight, Value
|
|
end type TItem
|
|
type(TItem), dimension(0:NUM_ITEMS-1) :: ITEMS
|
|
integer, dimension(0:NUM_ITEMS, 0:MAX_WEIGHT) :: D
|
|
integer :: I, W, V, MaxWeight
|
|
! Init Arrays
|
|
d = 0
|
|
ITEMS = [ TItem('compass', 13, 35), &
|
|
TItem('water', 153, 200), &
|
|
TItem('sandwich', 50, 160), &
|
|
TItem('glucose', 15, 60), &
|
|
TItem('tin', 68, 45), &
|
|
TItem('banana', 27, 60), &
|
|
TItem('apple', 39, 40), &
|
|
TItem('cheese', 23, 30), &
|
|
TItem('beer', 52, 10), &
|
|
TItem('suntan cream', 11, 70), &
|
|
TItem('camera', 32, 30), &
|
|
TItem('T-shirt', 24, 15), &
|
|
TItem('trousers', 48, 10), &
|
|
TItem('umbrella', 73, 40), &
|
|
TItem('waterproof trousers', 43, 70), &
|
|
TItem('waterproof overclothes', 42, 75), &
|
|
TItem('note-case', 22, 80), &
|
|
TItem('sunglasses', 7, 20), &
|
|
TItem('towel', 18, 12), &
|
|
TItem('map', 9, 150), &
|
|
TItem('socks', 4, 50), &
|
|
TItem('book', 30, 10) ]
|
|
!
|
|
do I = 0, NUM_ITEMS-1
|
|
do W = 0, MAX_WEIGHT
|
|
if (ITEMS(I)%Weight > W) then
|
|
D(I+1, W) = D(I, W)
|
|
else
|
|
D(I+1, W) = max(D(I, W), D(I, W - ITEMS(I)%Weight) + ITEMS(I)%Value)
|
|
end if
|
|
end do
|
|
end do
|
|
W = MAX_WEIGHT
|
|
V = D(NUM_ITEMS, W)
|
|
MaxWeight = 0
|
|
!
|
|
write(*, "(/,'bagged:')")
|
|
do I = NUM_ITEMS-1, 0, -1 !Pete
|
|
if (D(I+1, W) == V) then
|
|
if((D(I, (W - ITEMS(I)%Weight)) == V - ITEMS(I)%Value)) then
|
|
write(*, "(' ', A,t25,i0,t35,i0)", advance='yes') ITEMS(I)%Name,ITEMS(I)%weight,ITEMS(I)%value
|
|
MaxWeight = MaxWeight + ITEMS(I)%Weight
|
|
W = W - ITEMS(I)%Weight
|
|
V = V - ITEMS(I)%Value
|
|
end if
|
|
end if
|
|
end do
|
|
!
|
|
write(*, "('value = ', I0)") D(NUM_ITEMS, MAX_WEIGHT)
|
|
write(*, "('weight = ', I0)") MaxWeight
|
|
end program Knapsack01
|