[futurebasic] Knapsack Algorithm

Message: < previous - next > : Reply : Subscribe : Cleanse
Home   : February 2008 : Group Archive : Group : All Groups

From: Ken Shmidheiser <kshmidheiser@...>
Date: Wed, 27 Feb 2008 09:22:07 -0500
In the related previous thread, "i++ vs ++i," Robert Purves answered  
a nested loop question in C. Thank you Robert. I had tried nested  
whiles but never thought to break up the long ifs.

For anyone interested, here's an FB translation of the Knapsack  
algorithm as very nicely explained here:

    http://compprog.wordpress.com/2007/11/20/the-0-1-knapsack-problem/

and the referring page:

    http://snippets.dzone.com/tag/c

Both of which you may find of interest.

Ken

p.s. I really like the design of the wordpress page


Note: Adjust following code for line breaks


'--------------- BEGIN CODE -----------------

/*

    Knapsack Problem Algorithm

    Based on C Code at:

    http://compprog.wordpress.com/2007/11/20/the-0-1-knapsack-problem/

    FB Translation by Ken Shmidheiser
    with assistance from Robert Purves

    Feb. 27, 2008

*/

_maxWeight = 100

// The number of objects
dim as long n : n = 3

// c(i) is the *COST* of the ith object
// i.e. what YOU PAY to take the object
dim as long c(10)
c(0) = 8
c(1) = 6
c(2) = 4

// v(i) is the *VALUE* of the ith object
// i.e. what YOU GET for taking the object
dim as long v(10)
v(0) = 16
v(1) = 10
v(2) = 7

// The maximum weight you can take
dim as long weight : weight = 10

local fn FillKnapsack
'~'1
// a(i) holds the maximum value
// that can be obtained using at most i weight
dim as long a( _maxWeight )

// I use this to calculate which object were added
dim as long last_added( _maxWeight )
dim as long i, j
dim as long aux

for i = 0 to weight
a(i) = 0
last_added(i) = -1
next

a(0) = 0
i = 1
while ( i <= weight )
j = 0
while ( j < n )
long if ( c(j) <= i )
long if ( a(i) < a(i - c(j)) + v(j) )
a(i) = a(i - c(j)) + v(j)
last_added(i) = j
end if
end if
j++
wend
i++
wend

for i = 0 to weight
long if ( last_added(i) != -1 )
print "Weight"; i; "; Benefit:"; a(i);¬
" To reach this weight I added object:"; last_added(i) + 1,¬
using "(Cost $###.##"; v(last_added(i)); " ";¬
c(last_added(i)); "Kg) to weight"; i - c(last_added(i))
xelse
print "Weight"; i; "; Benefit: 0 Can't reach this exact weight."
end if
next

print "---"

aux = weight
while (( aux > 0 ) and ( last_added( aux ) != -1 ))
print "Added object:"; last_added(aux),¬
using "($###.##";v( last_added( aux ));¬
c( last_added( aux )); "Kg). Space left:";¬
aux - c( last_added( aux ))

aux -= c( last_added( aux ))

wend

print "Total value added:"; using "$###.##";a( weight )

end fn

window 1,,(0,0)-(600,300)
text _monaco, 10

fn FillKnapsack

do
HandleEvents
until gFBQuit