Rosetta Code

Knapsack problem/0-1: Difference between revisions

Page Discussion

Knapsack problem/0-1 (view source)

Revision as of 19:00, 26 June 2022

1,346 bytes removed ,  1 year ago
→‎{{header|FutureBasic}}
Line 3,073:
 
=={{header|FutureBasic}}==
<lang futurebasic>window 1, @"Knapsack Problem", (0,0,480,270)
 
_maxWeight = 400
def tab 20
 
void local fn FillKnapsack
_numberOfObjects = 21
long totalWeight = 0, totalValue = 0, itemWeight, unusedWeight
_weightOfKnapsack = 400
CFDictionaryRef item, extraItem = NULL
 
SortDescriptorRef sd
short n : n = _numberOfObjects /* The number of objects available to pack */
CFMutableArrayRef packedItems
Str31 s(_numberOfObjects) /* The names of available objects */
short c(_numberOfObjects) /* The *COST* of the ith object i.e. how much weight you must carry to pack the object */
short v(_numberOfObjects) /* The *VALUE* of the ith object i.e. on a scale of 1 to 200, how important is it that the object included */
short W : W = _weightOfKnapsack /* The maximum weight your knapsack will carry in ounces*/
 
s(0) = "map"
s(1) = "compass"
s(2) = "water"
s(3) = "sandwich"
s(4) = "glucose"
s(5) = "tin"
s(6) = "banana"
s(7) = "apple"
s(8) = "cheese"
s(9) = "beer"
s(10) = "suntan cream"
s(11) = "camera"
s(12) = "T-shirt"
s(13) = "trousers"
s(14) = "umbrella"
s(15) = "waterproof pants"
s(16) = "raincoat"
s(17) = "note-case"
s(18) = "sunglasses"
s(19) = "towel"
s(20) = "socks"
s(21) = "socks"
 
c(0) = 9
c(1) = 13
c(2) = 153
c(3) = 50
c(4) = 15
c(5) = 68
c(6) = 27
c(7) = 39
c(8) = 23
c(9) = 52
c(10) = 11
c(11) = 32
c(12) = 24
c(13) = 48
c(14) = 73
c(15) = 42
c(16) = 43
c(17) = 22
c(18) = 7
c(19) = 18
c(20) = 4
c(21) = 30
 
v(0) = 150
v(1) = 35
v(2) = 200
v(3) = 160
v(4) = 60
v(5) = 45
v(6) = 60
v(7) = 40
v(8) = 30
v(9) = 10
v(10) = 70
v(11) = 30
v(12) = 15
v(13) = 10
v(14) = 40
v(15) = 70
v(16) = 75
v(17) = 80
v(18) = 20
v(19) = 12
v(20) = 50
v(21) = 10
 
 
local fn FillKnapsack
short cur_w
double tot_v : tot_v = 0
short i, maxi, finalWeight : finalWeight = 0
short finalValue : finalValue = 0
short used(_numberOfObjects)
forCFArrayRef iitems = 0 to n@[
@{@"item":@"map", @"weight":@9, @"value":@150},
used(i) = 0
@{@"item":@"compass", @"weight":@13, @"value":@35 },
next
@{@"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 )
cur_w = W
items = fn ArraySortedArrayUsingDescriptors( items, @[sd] )
while cur_w > -1
packedItems = fn MutableArrayWithCapacity(0)
for item maxiin = -1items
itemWeight = fn NumberIntegerValue(item[@"weight"])
if ( totalWeight + itemWeight <= _maxWeight )
BeginCCode
for MutableArrayAddObject( i = 0; i <packedItems, n;item ++i)
totalWeight += itemWeight
if ((used[i] == 0) && ((maxi == -1) || ((float)v[i]/c[i] > (float)v[maxi]/c[maxi])))
totalValue += fn NumberIntegerValue(item[@"value"])
maxi = i;
EndC
used(maxi) = 1
cur_w -= c(maxi)
tot_v += v(maxi)
if (cur_w >= 0)
print s(maxi), c(maxi), v(maxi)
finalWeight = finalWeight + c(maxi)
finalValue = finalValue + v(maxi)
else
print
print "Add"; int( ( (double)cur_w/c(maxi) * 100 ) +100 ); "% more of "; s(maxi); " into the knapsack to fill remaining space."
tot_v -= v(maxi)
tot_v += (1 + (double )cur_w/c(maxi)) * v(maxi)
end if
wendnext
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
print "Filled the bag with objects whose total value is"; finalValue; "."
print "Total weight of packed objects is"; finalWeight; " ounces."
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
 
short i, totalValue, totalWeight
 
print
print "Available Items", "Weight in ounces", "Value (Scale of 1 to 200)"
for i = 0 to _numberOfObjects
print s(i), c(i), v(i)
totalValue += v(i)
totalWeight += c(i)
next
 
print
print "Total capacity of knapsack:"; W; " ounces"; "."
print "Total value of all"; _numberOfObjects; " objects:"; totalValue; "."
print "Total weight of all"; _numberOfObjects; " objects:"; totalWeight; " ounces."
print
print
print "Most optimal packing considering weight and value:"
print
print "Item", "Weight", "Value"
 
fn FillKnapsack
 
HandleEvents</lang>
 
{{output}}
<pre>
Item Weight Value
water 153 200
sandwich 50 160
map 9 150
note-case 22 80
waterproof overclothes 43 75
suntan cream 11 70
waterproof trousers 42 70
glucose 15 60
banana 27 60
socks 4 50
compass 13 35
sunglasses 7 20
 
knapsack 396 1030
[[Available]] Items Weight in ounces Value (Scale of 1 to 200)
map 9 150
compass 13 35
water 153 200
sandwich 50 160
glucose 15 60
tin 68 45
banana 27 60
apple 39 40
cheese 23 30
beer 52 10
suntan cream 11 70
camera 32 30
T-shirt 24 15
trousers 48 10
umbrella 73 40
waterproof pants 42 70
raincoat 43 75
note-case 22 80
sunglasses 7 20
towel 18 12
socks 4 50
socks 30 10
 
Total capacity of knapsack: 400 ounces.
Total value of all 21 objects: 1272.
Total weight of all 21 objects: 803 ounces.
 
 
Most optimal packing considering weight and value:
 
Item Weight Value
map 9 150
socks 4 50
suntan cream 11 70
glucose 15 60
note-case 22 80
sandwich 50 160
sunglasses 7 20
compass 13 35
banana 27 60
raincoat 43 75
waterproof pants 42 70
water 153 200
 
Add 17% more of cheese into the knapsack to fill remaining space.
 
Filled the bag with objects whose total value is 1030.
Total weight of packed objects is 396 ounces.
</pre>
 
Bernie
408

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/139465"