154 lines
3.1 KiB
Plaintext
154 lines
3.1 KiB
Plaintext
output file "Knapsack Problem Solution"
|
|
|
|
include "ConsoleWindow"
|
|
|
|
def tab 20
|
|
|
|
_numberOfObjects = 21
|
|
_weightOfKnapsack = 400
|
|
|
|
dim as short n : n = _numberOfObjects /* The number of objects available to pack */
|
|
dim as Str31 s(_numberOfObjects) /* The names of available objects */
|
|
dim as short c(_numberOfObjects) /* The *COST* of the ith object i.e. how much weight you must carry to pack the object */
|
|
dim as 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 */
|
|
dim as 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
|
|
dim as short cur_w
|
|
dim as double tot_v : tot_v = 0
|
|
dim as short i, maxi, finalWeight : finalWeight = 0
|
|
dim as short finalValue : finalValue = 0
|
|
dim as short used(_numberOfObjects)
|
|
|
|
for i = 0 to n
|
|
used(i) = 0
|
|
next
|
|
|
|
cur_w = W
|
|
while cur_w > -1
|
|
|
|
maxi = -1
|
|
|
|
BeginCCode
|
|
for ( i = 0; i < n; ++i)
|
|
if ((used[i] == 0) && ((maxi == -1) || ((float)v[i]/c[i] > (float)v[maxi]/c[maxi])))
|
|
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
|
|
wend
|
|
|
|
print
|
|
print "Filled the bag with objects whose total value is"; finalValue; "."
|
|
print "Total weight of packed objects is"; finalWeight; " ounces."
|
|
|
|
end fn
|
|
|
|
dim as 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
|