Recursion and Dynamic Programming

0/1 Knapsack (Small)

Fill a small 0/1 knapsack table where each row decides whether one more item is available.

Algorithm

@steps

  1. Create a table with one extra row for using zero items.
  2. Process the four items in fixed order.
  3. For each capacity, inherit when the item is too heavy.
  4. Otherwise compare skip and take from the previous row.
  5. Print the best value and the full deterministic table. @end @complexity
  • Time: O(item_count * capacity)
  • Space: O(item_count * capacity) @end
state transition `dp[i][w]` compares skipping item `i` with taking it and reading the remaining capacity from the previous row.

Fortran DSA Implementation

basic.f90 
program main
  implicit none
  integer :: weights(4), values(4), dp(0:4,0:5)
  integer :: item, cap, weight, value, skip, take
  weights = [2, 3, 4, 5]
  values = [3, 4, 5, 6]
  dp = 0
  do item = 1, 4
    weight = weights(item)
    value = values(item)
    do cap = 0, 5
      if (weight > cap) then
        dp(item, cap) = dp(item - 1, cap)
      else
        skip = dp(item - 1, cap)
        take = value + dp(item - 1, cap - weight)
        dp(item, cap) = max(skip, take)
      end if
    end do
  end do
  print '(I0)', dp(4,5)
  call print_table(dp)
contains
  subroutine print_table(table)
    integer, intent(in) :: table(0:4,0:5)
    integer :: i, w
    write(*, '(A)', advance='no') '['
    do i = 0, 4
      if (i > 0) write(*, '(A)', advance='no') ', '
      write(*, '(A)', advance='no') '['
      do w = 0, 5
        if (w > 0) write(*, '(A)', advance='no') ', '
        write(*, '(I0)', advance='no') table(i,w)
      end do
      write(*, '(A)', advance='no') ']'
    end do
    print '(A)', ']'
  end subroutine print_table
end program main

@end @output 7 [[0, 0, 0, 0, 0, 0], [0, 0, 3, 3, 3, 3], [0, 0, 3, 4, 4, 7], [0, 0, 3, 4, 5, 7], [0, 0, 3, 4, 5, 7]] @end