# knapsack.frink

``` /** This file contains solvers for various knapsack problems.     See:     Knapsack Problems book:     http://www.or.deis.unibo.it/kp.html     http://hjemmesider.diku.dk/~pisinger/codes.html     https://www.algorist.com/problems/Knapsack_Problem.html     https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/     https://en.m.wikipedia.org/wiki/Knapsack_problem     THINK ABOUT: What to return when no solution is found. */ /** This is a solver for the 0/1 knapsack problem.       It takes an array of integer values, array of integer weights,     and an integer capacity.  It tries to optimize so that the sum of values     is the largest for which the sum of the weights is less than or equal to     capacity.     it returns:       [maxvalue, indices, values, weights]     where        maxvalue:  The sum of the values in the best-fitting packing        indices :  An array of the indices selected        values  :  An array of the values selected        weights :  An array of the weights selected     This algorithm is O(capacity * numElements) in space and time     which is inefficient if the capacity is large.     Enumerating all the subsets would be O(2^numElements).  For example, with     a capacity of 6404180 and 24 elements, this algorithm evaluates     153,700,320 cases, where evaluating the 2^24 subsets would be only      16,777,216 cases.  Another algorithm should be chosen when the capacity     is large.     This algorithm is adapted from:     https://www.es.ele.tue.nl/education/5MC10/Solutions/knapsack.pdf */ knapsack[values, weights, capacity] := {    n = length[values]        if length[weights] != n    {       println["knapsack:  length of values does not equal length of weights."]       return undef    }    V = new array[[n+1, capacity+1], 0]    keep = new array[[n+1, capacity+1], false]    for i = 1 to n    {       for w = 0 to capacity       {          if weights@(i-1) <= w and (values@(i-1) + V@(i-1)@(w - weights@(i-1)) > V@(i-1)@w)          {             V@i@w = values@(i-1) + V@(i-1)@(w-weights@(i-1))             keep@i@w = true          } else          {             V@i@w = V@(i-1)@w             keep@i@w = false          }       }    }    included = new array    K = capacity    for i = n to 1 step -1       if keep@i@K == true       {          included.push[ [i-1, values@(i-1), weights@(i-1)] ]          K = K - weights@(i-1)       }    return concat[V@n@capacity, included.transpose[]] } /** Brute-force algorithm for evaluating the knapsack problem.  The time     complexity is O(2^numElements) so this is unfeasible if there is a large     number of elements.  However, as noted above, this is can be significantly     more efficient than the above algorithm if the capacity is large.     This also works with floating-point numbers or units of measure.     It takes an array of values, array of weights,     and a capacity.  It tries to optimize so that the sum of values     is the largest for which the sum of the weights is less than or equal to     capacity.     it returns:       [maxvalue, indices, values, weights]     where        maxvalue:  The sum of the values in the best-fitting packing        indices :  An array of the indices selected        values  :  An array of the values selected        weights :  An array of the weights selected */ knapsackBrute[values, weights, capacity] := {    n = length[values]        if length[weights] != n    {       println["knapsack:  length of values does not equal length of weights."]       return undef    }    // Make a bunch of loops that alternate between false and true.    loops = makeArray[[n], [false, true]]    // This is to make this work with units of measure.    zeroWeight = 0 weights@0    zeroValue  = 0 values@0    bestValue = zeroValue    bestIndices = undef        LOOP:    multifor v = loops    {       weight = zeroWeight       value  = zeroValue       for i = 0 to n-1          if v@i          {             weight = weight + weights@i             if weight > capacity                next LOOP i             value = value + values@i          }       if value > bestValue       {          bestValue = value          bestIndices = v.shallowCopy[]       }    }    // Build the result    indices = new array    outValues = new array    outWeights = new array        for i = 0 to n-1       if bestIndices@i       {          indices.push[i]          outValues.push[values@i]          outWeights.push[weights@i]       }    return [bestValue, indices, outValues, outWeights] } /** Brute-force algorithm for evaluating the multiple-choice knapsack problem     (MCKP).  Each weight or value is an array of choices from which exactly     one item is selected.     See sectoin 2.12 in http://www.or.deis.unibo.it/kp.html     The time complexity is O(choices^numElements) so this is unfeasible if     there is a large number of elements.     This also works with floating-point numbers or units of measure.     It takes an array of array of values, array of array of weights,     and a capacity.  It tries to optimize so that the sum of values     is the largest for which the sum of the weights is less than or equal to     capacity.     it returns:       [maxvalue, indices, values, weights]     where        maxvalue:  The sum of the values in the best-fitting packing        indices :  An array of the indices selected        values  :  An array of the values selected        weights :  An array of the weights selected */ knapsackMultiBrute[values, weights, capacity] := {    n = length[values]        if length[weights] != n    {       println["knapsack:  length of values does not equal length of weights."]       return undef    }    // Make a bunch of loops that alternate between the weights    loops = new array    for i=0 to n-1       loops.push[rangeOf[weights@i]]    // This is to make this work with units of measure.    zeroWeight = 0 weights@0@0    zeroValue  = 0 values@0@0    bestValue = zeroValue    bestIndices = undef        LOOP:    multifor v = loops    {       weight = zeroWeight       value  = zeroValue       for i = 0 to n-1       {          vi = v@i          weight = weight + weights@i@vi          if weight > capacity             next LOOP i          value = value + values@i@vi       }       if value > bestValue       {          bestValue = value          bestIndices = v.shallowCopy[]       }    }    // Build the result    indices = new array    outValues = new array    outWeights = new array    for i = 0 to n-1    {       bi = bestIndices@i       indices.push[bi]       outValues.push[values@i@bi]       outWeights.push[weights@i@bi]    }    return [bestValue, indices, outValues, outWeights] } /** Returns all the solutions for the subset-sum problem, that is, finds all     the subsets of the input that sum to a desired number. */ subsetSum[vals, target] := {    select[toSet[vals].subsets[], {|x, t| sum[x] == t}, target] } /** Returns all the solutions for the subset-product problem, that is, finds all     the subsets of the input that multiply to a desired number. */ subsetProduct[vals, target] := {    select[toSet[vals].subsets[], {|x, t| product[x] == t}, target] } /** This uses dynamic programming to find a maximum value for the subset-sum     problem for integers.  That is, it finds the largest subset of weights     which sum to target *or less.*     arguments: [weights, target]       weights:  an array of integers       target:   an integer that we want to sum to.     returns [max, weights]     Where       max: an integer containing the sum       weights:  an array of values that sum to target or less     TODO:  Adopt the code from knapsack and simplify it to not pass in weights            twice. */ maxSubsetSum[weights, target] := {    [maxvalue, indices, values] = knapsack[weights, weights, target]    return [maxvalue, values] } /** This is a solver for the "partition problem": given a set of numbers W,     it is desired to separate these numbers into two subsets W1 and W2 so that     the sums of the numbers in each subset are equal.     The partition problem is a special case of the subset sum problem, in     which the target sum is one half the sum of the entire set W.     args:       weights: An array of numeric values     returns:        an array of pairs [W1, W2] where W1 and W2 are the subsets. */ equalPartitions[weights] := {    result = new array    sum = sum[weights] / 2    if ! isInteger[sum]       return result        for sol = subsetSum[weights, sum]    {       s = deepCopy[weights]       for elem = sol          s.removeValue[elem]       result.push[ [sol, s] ]    }           return result }```