74 lines
2.9 KiB
Plaintext
74 lines
2.9 KiB
Plaintext
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
|