window 1, @"Knapsack Problem", (0,0,480,270)

_maxWeight = 400

void local fn FillKnapsack
  long              totalWeight = 0, totalValue = 0, itemWeight, unusedWeight
  CFDictionaryRef   item, extraItem = NULL
  SortDescriptorRef sd
  CFMutableArrayRef packedItems

  CFArrayRef items = @[
  @{@"item":@"map",                    @"weight":@9,   @"value":@150},
  @{@"item":@"compass",                @"weight":@13,  @"value":@35 },
  @{@"item":@"water",                  @"weight":@153, @"value":@200},
  @{@"item":@"sandwich",               @"weight":@50,  @"value":@160},
  @{@"item":@"glucose",                @"weight":@15,  @"value":@60 },
  @{@"item":@"tin",                    @"weight":@68,  @"value":@45 },
  @{@"item":@"banana",                 @"weight":@27,  @"value":@60 },
  @{@"item":@"apple",                  @"weight":@39,  @"value":@40 },
  @{@"item":@"cheese",                 @"weight":@23,  @"value":@30 },
  @{@"item":@"beer",                   @"weight":@52,  @"value":@10 },
  @{@"item":@"suntan cream",           @"weight":@11,  @"value":@70 },
  @{@"item":@"camera",                 @"weight":@32,  @"value":@30 },
  @{@"item":@"T-shirt",                @"weight":@24,  @"value":@15 },
  @{@"item":@"trousers",               @"weight":@48,  @"value":@10 },
  @{@"item":@"umbrella",               @"weight":@73,  @"value":@40 },
  @{@"item":@"waterproof trousers",    @"weight":@42,  @"value":@70 },
  @{@"item":@"waterproof overclothes", @"weight":@43,  @"value":@75 },
  @{@"item":@"note-case",              @"weight":@22,  @"value":@80 },
  @{@"item":@"sunglasses",             @"weight":@7,   @"value":@20 },
  @{@"item":@"towel",                  @"weight":@18,  @"value":@12 },
  @{@"item":@"socks",                  @"weight":@4,   @"value":@50 },
  @{@"item":@"book",                   @"weight":@30,  @"value":@10 }
  ]

  sd = fn SortDescriptorWithKey( @"value", NO )
  items = fn ArraySortedArrayUsingDescriptors( items, @[sd] )
  packedItems = fn MutableArrayWithCapacity(0)
  for item in items
    itemWeight = fn NumberIntegerValue(item[@"weight"])
    if ( totalWeight + itemWeight <= _maxWeight )
      MutableArrayAddObject( packedItems, item )
      totalWeight += itemWeight
      totalValue += fn NumberIntegerValue(item[@"value"])
    end if
  next

  text @"Menlo-Bold",,, fn ColorWithRGB(1.0,0.0,1.0,0.25),, 170
  print @"Item",@"Weight",@"Value"
  text @"Menlo",,, fn ColorClear
  for item in packedItems
    printf @"%@\t%6ld\t%5ld",item[@"item"],fn NumberIntegerValue(item[@"weight"]),fn NumberIntegerValue(item[@"value"])
  next
  text ,,, fn ColorWithRGB(1.0,0.0,1.0,0.25)
  printf @"knapsack\t%6ld\t%5ld",totalWeight,totalValue

  text
  print

  unusedWeight = _maxWeight - totalWeight

  for item in items
    if ( fn NumberIntegerValue(item[@"weight"]) <= unusedWeight )
      extraItem = item : break
    end if
  next

  if ( extraItem ) then printf @"There's just enough room for extra %@!", extraItem[@"item"]
end fn

fn FillKnapsack

HandleEvents