I was recently asked this problem in an interview and I couldn't solve it. Need some help on how to solve this problem.
Given a K-ary tree with N nodes (N <= 2000 and K <= 12) you need to assign some colour to each node.
Also, each node has a value associated with it which is equal to the number of units of paint required to color it (this value is <= X (defined below) ).
Now you have an infinite number of bucket of paints each having different color available to buy but a fixed capacity of 'X' units which is same for each bucket (X <= 30).
Also there is a constraint that you can only choose a node for coloring once all nodes lying on the path from root of the tree to this particular node have been colored so you always have to start coloring from the root and then proceed.
The buying operation is sequential (You only buy the next paint bucket once you have completely used the previous).
Also each node should be completely colored with one color only. So, if you choose a bucket of paint and color a node using some units of paint from that bucket and there is no available node satisfying the constraint which you can color using the remaining paint from that bucket, then you will have to throw this bucket and buy the next bucket of paint for the next node.
You need to find out the minimum number of cans of paint that you will have to buy to color all nodes of this tree.
The best possible solution that I could think of was doing a DP with a bitmask as a state that denotes the nodes that I've not chosen so far but that has an asymptotic complexity of O(2^N * N) which is too slow for the given values of N. Can somebody think of a solution that works for the given constraints?