0

I have a question based on the one posted here:

Combination problem with constraints

We have 4 containers and one pitcher of water that holds 100L. Each container has different capacities with maximums of, 70L, 45L, 33L and 11L levels respectively.

We can solve the number of all possible combinations that a total of 100L of water can be poured among a number of containers, using dynamic programming. In this case, it would be 14948.

As https://math.stackexchange.com/users/8508/robert-israel did it in the post above, we have:

F(100,4) = \sum_{x=0}^{11} F(100-x,3)

Now I'm trying to generate in a matrix the whole 14948 solutions, but how is it possible to generate only the combinations that match the constraint?

It seems like I can't use DP to create the solutions, because each state (y,j) depends on the previous state (y,j-1) and (y-1,j) (with (y,j) the number of solutions of x1+…+xj=y), which means that it doesn't seem feasible to construct the solutions of the new state (y,j) where the sum needs to be j upon a previous state where the sum needs to be j-1 .

Any suggestions?

Community
  • 1
Ouriel
  • 3

1 Answers1

0

Think of the solutions as vertices of a graph. Add an edge between two solutions $(a, b, c, d)$ and $(a', b', c', d')$ if the latter can be obtained from the former by exchanging $1$ liter of water between two containers. (For example, there should be an edge between $(60, 20, 20, 0)$ and $(59, 21, 20, 0)$.)

Then, to get all the solutions, run a breath first search starting from any valid solution (e.g. $(70, 30, 0, 0)$).

(You don't need to explicitly build the graph!)

dani_s
  • 1,610
  • 11
  • 12
  • Should I use the same concept for let's say 10 containers for example? to run a search starting from any valid solution would mean that I first write down one solution. Any idea how this can be done knowing that I want to have the number of containers, the sum (100L in this case) and the constraints on the sup (70L, 45L, 33L and 11L) as inputs in my function? – Ouriel Mar 13 '14 at 17:57
  • Yes it works for any number of containers, but I guess the number of solutions would be pretty large. (I'm assuming you actually want to enumerate all the solutions, there are obviously better ways if you only need to count them.) – dani_s Mar 13 '14 at 18:02
  • @Ouriel you can just fill the first containers until the pitcher is empty. For example if the pitcher contains $200$L and you have $6$ the containers with maximum capacity $80, 60, 50, 40, 30, 15$, then a solution would be $(80, 60, 50, 10, 0, 0)$ – dani_s Mar 13 '14 at 18:44