Unbounded knapsack with no similar consecutive elements

yumyum77 — Today at 10:51 AM
oh crap I have not seen a 12 pack of eggs and therefore bought another pack now I have 26 eggs, including the two in my current pack what should I do?

tougenkyou — Today at 11:14 AM
yumyum77 is the type of person that math problem writers use as an example

apt-get — Today at 11:17 AM
assuming that yumyum knows three recipes: one that uses two eggs, one three, and one five, and that he does not want to eat the same meal two days in a row Build yumyum a meal schedule such that he is left with no eggs by the end

apt-get — Today at 11:20 AM
hmm, it's too easy with 26 eggs

def backtrack(eggs):
  res = []
  stk = []

  def rec(eggs):
    if eggs == 0:
      res.append(stk[:])
    for meal in [2,3,5]:
      if len(stk) > 0 and meal == stk[-1]:
        continue
      if eggs - meal >= 0:
        stk.append(meal)
        rec(eggs-meal)
        stk.pop()
  rec(eggs)
  return res

eggs = 26
solutions = backtrack(eggs)
print(len(solutions), solutions)
print("all solutions are valid", all(map(lambda x: sum(x) == eggs, solutions)))

67 [[2, 3, 2, 3, 2, 5, 2, 5, 2], [2, 3, 2, 3, 5, 3, 5, 3], [2, 3, 2, 5, 2, 3, 2, 5, 2], [2, 3, 2, 5, 2, 5, 2, 3, 2], [2, 3, 2, 5, 2, 5, 2, 5], [2, 3, 5, 2, 5, 2, 5, 2], [2, 3, 5, 3, 2, 3, 5, 3], [2, 3, 5, 3, 5, 3, 2, 3], [2, 3, 5, 3, 5, 3, 5], [2, 5, 2, 3, 2, 3, 2, 5, 2], [2, 5, 2, 3, 2, 5, 2, 3, 2], [2, 5, 2, 3, 2, 5, 2, 5], [2, 5, 2, 3, 5, 2, 5, 2], [2, 5, 2, 5, 2, 3, 2, 3, 2], [2, 5, 2, 5, 2, 3, 2, 5], [2, 5, 2, 5, 2, 3, 5, 2], [2, 5, 2, 5, 2, 5, 2, 3], [2, 5, 2, 5, 2, 5, 3, 2], [2, 5, 2, 5, 3, 2, 5, 2], [2, 5, 3, 2, 5, 2, 5, 2], [2, 5, 3, 5, 3, 5, 3], [3, 2, 3, 2, 3, 2, 3, 5, 3], [3, 2, 3, 2, 3, 5, 3, 2, 3], [3, 2, 3, 2, 3, 5, 3, 5], [3, 2, 3, 2, 5, 3, 5, 3], [3, 2, 3, 5, 2, 3, 5, 3], [3, 2, 3, 5, 3, 2, 3, 2, 3], [3, 2, 3, 5, 3, 2, 3, 5], [3, 2, 3, 5, 3, 2, 5, 3], [3, 2, 3, 5, 3, 5, 2, 3], [3, 2, 3, 5, 3, 5, 3, 2], [3, 2, 5, 2, 5, 2, 5, 2], [3, 2, 5, 3, 2, 3, 5, 3], [3, 2, 5, 3, 5, 3, 2, 3], [3, 2, 5, 3, 5, 3, 5], [3, 5, 2, 3, 2, 3, 5, 3], [3, 5, 2, 3, 5, 3, 2, 3], [3, 5, 2, 3, 5, 3, 5], [3, 5, 2, 5, 3, 5, 3], [3, 5, 3, 2, 3, 2, 3, 2, 3], [3, 5, 3, 2, 3, 2, 3, 5], [3, 5, 3, 2, 3, 2, 5, 3], [3, 5, 3, 2, 3, 5, 2, 3], [3, 5, 3, 2, 3, 5, 3, 2], [3, 5, 3, 2, 5, 3, 2, 3], [3, 5, 3, 2, 5, 3, 5], [3, 5, 3, 5, 2, 3, 2, 3], [3, 5, 3, 5, 2, 3, 5], [3, 5, 3, 5, 2, 5, 3], [3, 5, 3, 5, 3, 2, 3, 2], [3, 5, 3, 5, 3, 2, 5], [3, 5, 3, 5, 3, 5, 2], [5, 2, 3, 2, 5, 2, 5, 2], [5, 2, 3, 5, 3, 5, 3], [5, 2, 5, 2, 3, 2, 5, 2], [5, 2, 5, 2, 5, 2, 3, 2], [5, 2, 5, 2, 5, 2, 5], [5, 3, 2, 3, 2, 3, 5, 3], [5, 3, 2, 3, 5, 3, 2, 3], [5, 3, 2, 3, 5, 3, 5], [5, 3, 2, 5, 3, 5, 3], [5, 3, 5, 2, 3, 5, 3], [5, 3, 5, 3, 2, 3, 2, 3], [5, 3, 5, 3, 2, 3, 5], [5, 3, 5, 3, 2, 5, 3], [5, 3, 5, 3, 5, 2, 3], [5, 3, 5, 3, 5, 3, 2]]
all solutions are valid True

so first i made a naive recursive backtracking solution which was O(2**number of eggs) in time complexity (you enumerate all the permutations, and whenever deciding to choose the next egg, you look at the last egg you choose and if it's the same you continue onto the next iteration)

03:51 <tougenkyou> now a more interesting solution is a dynamic programming one, imagine you formulate your recurrence as
03:51 <tougenkyou> ways(number of eggs, sequence ends in 5) = ways(eggs - 5, sequence ends in 3 or 2)
03:51 <tougenkyou> ways(number of eggs, sequence ends in 3) = ways(eggs - 3, sequence ends in 5 or 2)
03:51 <tougenkyou> ways(number of eggs, sequence ends in 2) = ways(eggs - 2, sequence ends in 3 or 5)
03:52 <tougenkyou> suppose you have 26 eggs, solve for ways(26, ends in 5) + ways(26, ends in 3) + ways(26, ends in 2)
03:53 <tougenkyou> your time complexity is now O(number of eggs, aka 26 * number of possible recipes you have, aka 3)
03:54 <tougenkyou> my conjecture is you cannot do better than this because if you pose it this way, it has to be an NP-hard problem
03:55 <tougenkyou> i don't see any way to turn it into a closed form solution, not least, because you can have solutions of different lengths
03:55 <tougenkyou> like [2, 3, 2, 3, 2, 5, 2, 5, 2] and [5, 3, 5, 3, 5, 3, 2]
03:58 <tougenkyou> you can use the principle of inclusion-exclusion to solve for "arrange a permutation of known size with no two adjacent numbers being the same" https://math.stackexchange.com/questions/439559/permutations-with-no-two-adjacent-numbers-being-equal but obviously here your size varies

def ways(MEALS, eggs):
  dp = [ [0]*len(MEALS) for _ in range(eggs + 1) ]
  # corresponds to..
  dp[0] = [1]*len(MEALS) # vacuously true
  for i in range(1, eggs+1):
    for j in range(len(MEALS)):
      for k in range(len(MEALS)):
        if k == j:
          continue
        if (i - MEALS[j]) < 0:
          continue
        dp[i][j] += dp[i - MEALS[j]][k]
  return sum(dp[-1]) // (len(MEALS)-1)

print("ways to get 26 eggs", ways([2,3,5], 26) ) # 67, may verify against the backtracking solution
# print("ways to get 30 eggs", ways(30) )
# print("ways to get 40 eggs", ways(40) )

TODO: how to construct an actual sequence of meals from the DP table

• Next:
• Previous: