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 19908 days, 5 hours, 32 minutes ago.