We present in this paper an approximative method for distributed combinatorial optimization problems based on dynamic programming. The algorithm is a utility propagation method and requires a linear number of messages. The largest message is in the worst case exponential in the width of the constraint graph, in case of exact computation. However, it can be tuned with 2 parameters that allow the user to specify the desired tradeoff between solution quality and computational complexity. The second part of this paper presents an anytime version of the first algorithm, which provides increasingly accurate solutions while the propagation is still in progress, thus being suitable for very large distributed problems. Although the algorithms presented here are distributed, their reduction to the centralized case is rather straightforward.