2

问题定义

我有n容量相同的水桶m，一个接一个。我可以将水从一个桶倒到它右边的那个。目标是将它们全部倒入另一个容器中，但只能清空最右边的桶。它们每个都有一定的初始水量w，其中0 <= w <= m和w是整数。从某种意义上说，如果您遇到以下情况：6 6 -> 3 9，您只倒 3，则您不能进行部分移动，这是不允许的。如果你倒，你必须尽可能多地倒，所以合法的移动是 6 6 -> 2 10。

为了清空所有的桶，我必须做的最少移动次数是多少？桶的最大数量为 1000，最大容量为 100。

例子

示例 1

4 桶容量 10 与以下水量：4 0 6

答案是 4 0 6 -> 0 4 6 -> 0 0 10 -> 0 0 0，即三步。

示例 2

3 桶容量 10, 8 9 3

8 9 3 -> 8 2 10 -> 0 10 10 -> 0 10 0 -> 0 0 10 -> 0 0 0 = 总共 5 次移动

我首先尝试使用不同类型的算法（贪婪、动态、回溯等），但似乎都没有。我以为我找到了一个非常直观的解决方案，但检查这些答案的程序告诉我这是错误的，所以我可能错了。另一件事是这个程序以前拒绝了正确的答案，所以我不太确定。

这是我的解决方案：

计算每个桶之前所有桶的总和，然后将该数字的上限除以桶的容量，然后将所有这些数字相加。

例如：6 6 6 6 6 -> 6 12 18 24 30

ceil(6/10) ceil(12/10) ceil(18/10) ceil(24/10) ceil(30/10) = 1 + 2 + 2 + 3 + 3 = 11

这是正确的答案：6 6 6 6 6 -> 6 2 10 6 6 -> 0 8 10 6 6 -> 0 8 10 2 10 -> 0 8 2 10 10 -> 0 0 10 10 10 -> 0 0 10 10 0 -> 0 0 10 0 10 -> 0 0 10 0 0 -> 0 0 0 10 0 -> 0 0 0 0 10 -> 0 0 0 0 0 = 11 步

逻辑是，如果L在某个桶之前有一升水，那么至少必须有ceil(L/Capacity)经过该位置的移动。到目前为止，我已经尝试了大约 30 个测试用例，它们都奏效了。每次我以为我找到了一个反例，我手动尝试了几次后才意识到我错了。问题是，虽然我很确定这是正确的答案，但我不知道如何证明这样的事情，否则我可能只是错了。

有人可以告诉我这个答案是否正确吗？

4

4 回答 4

-1

这不是一个解决方案，而是 Python 代码，它通过蛮力从给定配置中找到最小移动次数。尝试每个合法移动序列并报告最短长度。

B= [6, 6, 6, 6, 6] # Buckets state

M= sum(B) * len(B) # Gross upper bound
B.append(- sum(B)) # Append the container

def Try(N):
    global M

    # Check if we have found a better solution
    if B[-1] == 0 and N < M:
        M= N

    # Try every possible move from i to i+1
    for i in range(len(B) - 1):
        # Amount transferable
        D= min(B[i], 10 - B[i + 1])

        if D > 0:
            # Transfer
            B[i]-= D
            B[i + 1]+= D

            # Recurse
            Try(N+1)

            # Restore
            B[i]+= D
            B[i + 1]-= D

Try(0)
print M, "moves"

>>>
11 moves
于 2014-04-16T09:34:20.967 回答
-1

可以影响正确算法设计的几点：-

  1. 最右边的满桶是直接一次性的。只需要为 n 个最右边的桶添加 n*(n+1)/2 即可获得总步数。
  2. 如果最右边的桶未满，则检查前一个桶是否已满或能够填满最右边的桶，否则尝试填充该桶，递归执行此操作，直到满足任一条件或达到第一个桶。然后将桶倒入下一个，直到它满或其他是空的自下而上并计数步骤。
  3. 做 1 到 2 直到只剩下 1 个或没有桶
  4. 如果剩下一个桶，则将其清空。

例子 ：-

given 4 0 6 

1. fails 
2. last bucket is not empty hence try to pour second last but it is also empty 
   pour 4 into bucket 1 and then bucket 1 into bucket 2 . Hence after this step  
   4 0 6 => 0 4 6  => 0 0 10
3. 1 bucket left so 4
4. empty bucket 0 0 10 => 0 0 0




 given 8 9 3

   iteration 1 : 8 9 3 => 8 2 10 
   iteration 2 : 8 2 10 => 8 2 0  and  8 2 0 => 0 10 0
   iteration 3 : 0 10 0 => 0 0 10 => 0 0 0


 given 6 6 6 6 6

   iteration 1 : 6 6 6 6 6 => 6 6 6 2 10 
   iteration 2 : 6 6 6 2 10 => 6 6 6 2 0 && 6 6 6 2 0 => 6 2 10 2 0 => 6 2 2 10 0
   iteration 3 : 6 2 2 10 0 => 6 2 2 0 10 => 6 2 2 0 0 && 
                 6 2 2 0 0 => 0 8 2 0 0 => 0 0 10 0 0  
   iteration 4 : 0 0 10 0 0 => 0 0 0 10 0 => 0 0 0 0 10 => 0 0 0 0 0

时间复杂度：-直接实现将是因为在 1 次迭代中，至少 1 个最右边的桶在计算O(n^2)中被清空。O(n)

于 2014-04-16T11:17:40.763 回答
-1

有一个非常简单的解决方案。

已知最佳移动次数为Sum(0<=i<N: Pi\C)，其中\表示整数除以过量，Pi形式为 的前缀和B。

例子：

 6  6  6  6  6
 6 12 18 24 30
 1  2  2  3  3 => 11

总是选择将最佳数量减少一个单位的移动就足够了。这个移动可以在线性时间内找到N。（提示：找到一些Pi\C移动减少的东西。）

 2>10  6  6  6
 2 12 18 24 30
 1  2  2  3  3 => 11

 6  2>10  6  6
 6  8 18 24 30
 1  1* 2  3  3 => 10

 6  6  2>10  6
 6 12 14 24 30
 1  2  2  3  3 => 11

 6  6  6  2>10
 6 12 18 20 30
 1  2  2  2* 3 => 10

 6  6  6  6  0>
 6 12 18 24 24
 1  2  2  3  3 => 11

总复杂度为O(N.M)，其中M为最佳移动次数。

B= [6, 6, 6, 6, 6]
C= 10

# Show the current state
print B

 # Append the container
B.append(- sum(B))

# Loop until all buckets are empty
while B[-1] != 0:
    # Emulate the quotient by excess
    Prefix= C - 1

    # Try all buckets
    for i in range(len(B) - 1):        
        # Amount transferable
        A= min(B[i], C - B[i + 1])

        # Evaluate the move from i to i+1
        Prefix+= B[i]
        if (Prefix - A) / C < Prefix / C:
            # The total count will decrease, accept this move
            B[i]-= A
            B[i + 1]+= A
            break

    # Show the current state
    print B[:-1]

>>> 
[6, 6, 6, 6, 6]
[6, 2, 10, 6, 6]
[0, 8, 10, 6, 6]
[0, 8, 10, 2, 10]
[0, 8, 2, 10, 10]
[0, 0, 10, 10, 10]
[0, 0, 10, 10, 0]
[0, 0, 10, 0, 10]
[0, 0, 0, 10, 10]
[0, 0, 0, 10, 0]
[0, 0, 0, 0, 10]
[0, 0, 0, 0, 0]

算法终止的证明依赖于最优数公式的有效性，这还有待证明。

于 2014-04-16T15:13:20.600 回答
-1

这是我对这个问题的发现

首先让我们回顾一下游戏规则：

  • 规则 1：如果最右边的存储桶已装满，您只能将其全部丢弃

  • 规则 2：您可以根据需要（最多10-bucket[i+1]）从任何bucket[i]到bucket[i+1]

让我们考虑以下特殊情况：

  1. 移位：如果0, 10, 0, 0, 0您在处理前将第二个桶移位 3次

  2. 合并：如果2 4您可以将第一个存储桶合并到第二个存储桶以获得0 6

  3. 完美合并：如果6 4您合并到0 10第二个桶满，最佳完美合并将在当前桶中留下 0

结论：我建议以下策略，从左到右的从右到左顺序处置，采取完美合并并转移到处置。

注意：这不是这个问题的最佳算法

void solution (int bucket [], const int size)
{
    for (int i=size-1; i>=0; i--)
    {
        // find a non-empty bucket
        if (bucket[i] > 0)
        {
            // bucket need to be filled
            if (bucket[i] < 10)
                for (int j=i-1; j>=0; j--)
                {
                    // -------------------
                    // fill bucket[i] from previous
                    //        buckets and count moves
                    // -------------------

                    if (bucket[i] == 10)
                        break;
                }

            bucket[i]=0; // (size-i) shift + 1 dispose
            moves = moves + (size-i) + 1;
        }
    }
}
于 2014-04-16T08:39:02.703 回答