/** 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.

    TODO:  Maybe add a descriptor expression for each item type so we don't have
           to re-look them up by name.

    TODO:  Implement a solver for Rosetta Code problem:
     https://rosettacode.org/wiki/Knapsack_problem/Bounded
     Where there can be a variable number of pieces of each type.
*/

/** 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 section 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
}

/** This is a solver for the "bounded knapsack" problem.  The bounded knapsack
    problem differs from the 0/1 knapsack problem (solved by the knapsack
    function above) in that there can be a bounded count of each item.  For
    example, you may have 0 to 1 tubes of toothpaste but 0 to 5 chocolate bars.

    It takes an array of integer values, array of integer weights,
    array of integer maximum counts, 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.

    What this actually does is creates a mapping that can be solved with the
    0/1 knapsack mapper.  It does this by creating a binary set of multiples of
    each item.  For example, if there are 0-21 possible donuts that you can
    put into the knapsack, this creates multiples of 1,2,4, and 8 (which add up
    to 15) and a last multiple of the leftover of 6 (which adds up to 15+6=21)
    that can be added to the knapsack.  This results in a logarithmic factor of
    additional time needed.  The overall time becomes
    O(capacity * numElements * log2(meanCount)) where meanCount is the mean
    multiple of each item.  This routine then takes the artificial multiples
    and returns a true number of indices used and their multiples.

    it returns:
      [maxvalue, maxweight, usedDict]

    where
       maxvalue:  The sum of the values in the best-fitting packing
       maxweight: The sum of the weights in the best-fitting packing
       usedDict:  An dictionary of <index, count> pairs indicating how many
                  times each index was used.  If an index was not used, it
                  does not appear in the dictionary.
*/
knapsackBounded[values, weights, maxcount, capacity] :=
{
   len = length[values]
   
   if length[weights] != len or length[maxcount] != len
   {
      println["knapsackBounded:  length of values or counts does not equal length of weights."]
      return undef
   }

   values1  = new array
   weights1 = new array
   multipliers = new array  // Array of [origIndex, multiplier]

   ITEM:
   for i = 0 to len-1
   {
      count = maxcount@i

      if count == 1
      {
         values1.push[values@i]
         weights1.push[weights@i]
         multipliers.push[ [i, 1] ]
      } 

      if count > 1
      {
         nsum = 1
         multiplier = 1
         do
         {
            // Create multiples of 1,2,4,8... of the items
            values1.push[values@i * multiplier]
            weights1.push[weights@i * multiplier]
            multipliers.push[ [i, multiplier] ]
            multiplier = multiplier * 2
            nsum = nsum + multiplier
         } while nsum < count

         nsum = nsum - multiplier
         multiplier = multiplier / 2

         // We have leftovers; add one more multiple to use them all
         if nsum < count
         {
            diff = count - nsum
            values1.push[values@i * diff]
            weights1.push[weights@i * diff]
            multipliers.push[ [i, diff] ]
         }
      }
   }

   /*
   println["Values1: $values1"]
   println["Weights1: $weights1"]
   println["Multipliers: $multipliers"]
   println[]
   */
   
   [maxvalue2, indices2, values2, weights2] = knapsack[values1, weights1, capacity]

   /*
   println["Maxvalue2: $maxvalue2"]
   println["Values2: $values2"]
   println["Weights2: $weights2"]
   println["indices2: $indices2"]
   */

   used = new dict   // Dictionary of <origIndex, times>
   for idx = indices2
   {
      // Map multiples back to a count of originals
      [origIndex, times] = multipliers@idx
      used.increment[origIndex, times]
   }

   // println["used: $used"]

   return [maxvalue2, sum[weights2], used]
}

//println[knapsackBounded[[1,7], [1,5], [16, 3], 19]]