查找数字的组合，以求和到一个数字

Question

我有一个问题，我应该找到5l，10l和15l桶的组合来填充一个水库。例如，如果水库是30l，那么组合应该是15l和15l (这是最好的情况，当我们尽可能使用更大的水桶时)。

我看过回溯，但到目前为止运气不佳。算法应该使用Java。

Answer 1

这是一个经典的硬币变化问题，即NP问题。但是对于有限规模的问题，有一些动态规划方法来解决。有关详细信息，请参阅：

http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/

Change

problem

Answer 2

我不会给你写代码，但这会给你一个好主意。

检查最大(15升)是否小于水库。如果是的话，减少储油量，并注意已经选定了1x15L。使用越来越小的桶重复此操作，直到您没有剩下的(或剩余的)。