Knapsack problem/0-1: Difference between revisions
Content added Content deleted
| Line 3,073: | Line 3,073: | ||
=={{header|FutureBasic}}== |
=={{header|FutureBasic}}== |
||
<lang futurebasic> |
<lang futurebasic>window 1 |
||
output file "Knapsack Problem Solution" |
|||
include "ConsoleWindow" |
|||
def tab 20 |
def tab 20 |
||
| Line 3,160: | Line 3,157: | ||
local fn FillKnapsack |
local fn FillKnapsack |
||
dim as short cur_w |
dim as short cur_w |
||
dim as double tot_v : tot_v = 0 |
dim as double tot_v : tot_v = 0 |
||
dim as short i, maxi, finalWeight : finalWeight = 0 |
dim as short i, maxi, finalWeight : finalWeight = 0 |
||
dim as short finalValue : finalValue = 0 |
dim as short finalValue : finalValue = 0 |
||
dim as short used(_numberOfObjects) |
dim as short used(_numberOfObjects) |
||
for i = 0 to n |
for i = 0 to n |
||
used(i) = 0 |
used(i) = 0 |
||
next |
next |
||
cur_w = W |
cur_w = W |
||
while cur_w > -1 |
while cur_w > -1 |
||
maxi = -1 |
maxi = -1 |
||
BeginCCode |
BeginCCode |
||
for ( i = 0; i < n; ++i) |
for ( i = 0; i < n; ++i) |
||
if ((used[i] == 0) && ((maxi == -1) || ((float)v[i]/c[i] > (float)v[maxi]/c[maxi]))) |
if ((used[i] == 0) && ((maxi == -1) || ((float)v[i]/c[i] > (float)v[maxi]/c[maxi]))) |
||
maxi = i; |
maxi = i; |
||
EndC |
EndC |
||
used(maxi) = 1 |
used(maxi) = 1 |
||
cur_w -= c(maxi) |
cur_w -= c(maxi) |
||
tot_v += v(maxi) |
tot_v += v(maxi) |
||
if (cur_w >= 0) |
if (cur_w >= 0) |
||
print s(maxi), c(maxi), v(maxi) |
print s(maxi), c(maxi), v(maxi) |
||
finalWeight = finalWeight + c(maxi) |
finalWeight = finalWeight + c(maxi) |
||
finalValue = finalValue + v(maxi) |
finalValue = finalValue + v(maxi) |
||
else |
else |
||
print |
print |
||
print "Add"; int( ( (double)cur_w/c(maxi) * 100 ) +100 ); "% more of "; s(maxi); " into the knapsack to fill remaining space." |
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 -= v(maxi) |
||
tot_v += (1 + (double )cur_w/c(maxi)) * v(maxi) |
tot_v += (1 + (double )cur_w/c(maxi)) * v(maxi) |
||
end if |
end if |
||
wend |
wend |
||
print |
print |
||
print "Filled the bag with objects whose total value is"; finalValue; "." |
print "Filled the bag with objects whose total value is"; finalValue; "." |
||
print "Total weight of packed objects is"; finalWeight; " ounces." |
print "Total weight of packed objects is"; finalWeight; " ounces." |
||
end fn |
end fn |
||
| Line 3,211: | Line 3,208: | ||
print "Available Items", "Weight in ounces", "Value (Scale of 1 to 200)" |
print "Available Items", "Weight in ounces", "Value (Scale of 1 to 200)" |
||
for i = 0 to _numberOfObjects |
for i = 0 to _numberOfObjects |
||
print s(i), c(i), v(i) |
|||
totalValue += v(i) |
|||
totalWeight += c(i) |
|||
next |
next |
||
| Line 3,227: | Line 3,224: | ||
fn FillKnapsack |
fn FillKnapsack |
||
</lang> |
|||
HandleEvents</lang> |
|||
Output: |
Output: |
||