knapsackTest.frink

Download or view knapsackTest.frink in plain text format



/** This is a test for the 0/1 knapsack routines in knapsack.frink

    The test data comes from:

    https://people.sc.fsu.edu/~jburkardt/datasets/knapsack_01/knapsack_01.html
*/


use knapsack.frink

// Test with units of measure.
test[[60 dollars, 100 dollars, 120 dollars],
     [10 kg, 20 kg, 30 kg],
     50 kg,
     [0,1,1]]

// Test multiple choice knapsack
println[]
values = [[30 dollars, 60 dollars], [200 dollars, 140 dollars], [70 dollars, 120 dollars]]
weights = [[10 kg, 15 kg], [35 kg, 20 kg], [25 kg, 30 kg]]
println[knapsackMultiBrute[values, weights, 70 kg]]

for n = 1 to 8
{
   set = "0$n"
   println["\n\nTesting set $set"]
   capacity = eval[read["https://people.sc.fsu.edu/~jburkardt/datasets/knapsack_01/p${set}_c.txt"]]
   weights = eval[splitLines[trim[read["https://people.sc.fsu.edu/~jburkardt/datasets/knapsack_01/p${set}_w.txt"]]]]
   values = eval[splitLines[trim[read["https://people.sc.fsu.edu/~jburkardt/datasets/knapsack_01/p${set}_p.txt"]]]]
   optimal = eval[splitLines[trim[read["https://people.sc.fsu.edu/~jburkardt/datasets/knapsack_01/p${set}_s.txt"]]]]

   test[values, weights, capacity, optimal]
}

test[values, weights, capacity, optimal] :=
{
   println["Capacity is $capacity"]
   println["Number of values is " + length[values]]
   println["Values is $values"]
   println["Weights is $weights"]

   s = now[]
   [total, indices, outValues, outWeights] = knapsackBrute[values, weights, capacity]
   e = now[]

   println["Time: " + (e-s)]
   println["outValues is $outValues"]
   println["outWeights is $outWeights"]
   println["Total value is $total"]
   println["Total weights is " + sum[outWeights]]

   println["Indices chosen:  " + indices]
   optIndices = new array
   for i=0 to length[optimal]-1
      if optimal@i == 1
         optIndices.push[i]

   println["Optimal indices: " + indices]
   if toSet[indices] != toSet[optIndices]
      println["********** FAIL *********"]
}


Download or view knapsackTest.frink in plain text format


This is a program written in the programming language Frink.
For more information, view the Frink Documentation or see More Sample Frink Programs.

Alan Eliasen was born 20051 days, 23 hours, 13 minutes ago.