Knapsack problem/0-1: Difference between revisions
→{{header|FutureBasic}}
Line 3,073:
=={{header|FutureBasic}}==
<lang futurebasic>window 1
def tab 20
Line 3,160 ⟶ 3,157:
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
Line 3,211 ⟶ 3,208:
print "Available Items", "Weight in ounces", "Value (Scale of 1 to 200)"
for i = 0 to _numberOfObjects
next
Line 3,227 ⟶ 3,224:
fn FillKnapsack
HandleEvents</lang>
Output:
| |||