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