英文:
Efficient Algorithm for Amount allocation problem
问题
我在思考是否有一种有效的方法来解决以下问题。
我们有两组桶，它们由数字数组表示。数字是桶的大小。每组桶的大小和桶的数量都没有限制。但是两组桶的大小之和是相等的。例如：
groupA = [1, 2, 3, 4]
groupB = [3, 3, 2, 2]
如果组A的桶装满了水，组B的桶为空。在每一步中，我们可以从组A的一个桶中移动一定数量的水到组B的一个桶中。移动的水量不应超过组A桶中已有的水量和组B桶中剩余的空间。
问题是，找到一种在最少步骤内将所有组A中的水移动到组B的解决方案。
我知道可以使用蛮力搜索，但它似乎具有指数时间复杂度。贪婪算法可以使用，但我无法证明贪婪算法提供了最优解。
英文:
I am wondering if there is an efficient way to solve the following question.
We have 2 groups of buckets, which is represented by number arrays. The number is the bucket size. The bucket size and the number of buckets in each group is not limited. But the size sum of 2 group2 are equal. For example:
groupA = [1, 2, 3, 4]
groupB = [3, 3, 2, 2]
If buckets in group A are full of water and buckets in groupB are empty. In each step, we can move certain amount of water from one bucket in groupA to one bucket to groupB. The water amount should not exceed the existing amount in the groupA bucket and the left space in groupB bucket.
The question is, find a solution with minimum number of steps to move all water in groupA to groupB.
I know I can use the brute force search, but it looks to have an exponential time complexity. Greedy is ok, but I cannot prove greedy provides the optimal solution.
答案1
得分: 2
这有点棘手，但当贪婪算法是最优的时，A*搜索可以有效地证明。相同的技术也提供了动态规划的解决方案。
但这样做的代价是有时需要指数级的时间和内存。
英文:
The 3-partion problem can be solved with a solver for your problem, so there is no general efficient algorithm.
It is tricky, but an A* search can efficiently prove that greedy is optimal when it is. The same technique provides solutions if dynamic programming does.
But it does so at the cost of sometimes taking both exponential time and memory.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论