From: Ken Shmidheiser <kshmidheiser@...>

Date: Wed, 27 Feb 2008 09:22:07 -0500

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