受感染的鱼可以吃掉比自己小的鱼。所需的最少操作次数

Question

一位邪恶的科学家开发了一种注射剂，可以让鱼产生无法满足的饥饿感。在进行这种注射时，一条体型为 x 的鱼可以吃掉另一体型为 y (y < x) 的鱼，并成为体型为 x + y 的鱼，并保持这种饥饿感。水族馆里有许多大小不一的鱼。这位科学家将一条注射过的鱼放入这个水族箱，其中 objective 最后只剩下 1 条鱼。为了实现这一点，科学家只能进行两种类型的移动：添加任意大小的普通鱼或从水族箱中移除现有的普通鱼。给定水族箱中其他鱼的大小和注射鱼的大小，编写一个程序来确定科学家实现其 objective 所需的最少移动次数。例如，假设水族箱中有 5 条鱼，注入的鱼的尺寸为 10，其他鱼的尺寸为 9、20、25 和 100。为确保水族箱中只剩下 1 条鱼，科学家需要移除大小为 100 的鱼并添加一条大小为 3 的鱼。因此输出为 2。步骤顺序如下所示。每一步水族箱中鱼的大小都显示在花括号中。突出显示的数字是注射鱼的大小。

输入格式： {infectedFish} # {a,b,c,d ... } 其中 a,b,c 等是正常鱼

示例：

10#9,20,25,100 ===> 2
3#25,20,100,400,500 ===> 5
50#25,20,9,100 ===>0

我用下面的代码解决了这个问题。

 public static int count(int inf, int a[], int i, int op){

    //base case
    if(i==a.length){
      return op;
    }

    while(i<a.length && inf>a[i]){
      inf+=a[i];
      i++;
    }

    if(i==a.length){
      return op;
    }

    int curr = inf+inf-1;
    return Math.min(count(curr, a, i, op+1), count(inf, a, i+1, op+1));

  }

调用它使用，System.out.println(count(x, a, 0, 0)); x 是被感染的鱼，a 是给定的排序数组；

这种做法正确吗？如果是这样，它似乎有 comman 子问题，我们如何进行记忆？

Answer 1

让我们总结一下：

有两种可能的干预措施：
移除最大的鱼，然后添加一条比被感染的鱼小一点的鱼。

被感染的鱼可以吞噬所有较小的鱼，每次增长的大小都是被吃掉的鱼的大小。

你希望最少的干预次数只留下吞噬者。

一个更简单的算法是：

按大小对所有正常鱼进行排序。
简单的解决方案是手动移除所有鱼。
您还没有添加任何新鱼。
尽可能多地吞噬最小的鱼。
新的候选解决方案是添加的鱼加上剩余的鱼。选择一个更好的。
如果没有鱼，你就完成了。
根据需要经常添加一条 size-1 的鱼来吞噬最小的鱼，从而将吞噬者增加到 2*size-1。
继续第 4 步，吞食鱼。

Answer 2

您可以通过稍微修改您的算法来提高效率。

如果你要吃的鱼不止一条，最好不要去掉下一条，然后尝试吃更大的鱼。

当你吃鱼时，你变大了，没有任何代价。

因此，备选方案是：

长大后吃下一条鱼，即添加新鱼后
摆脱所有剩余的鱼

那么，公式可以简化如下，其他代码不变：

return Math.min(count(curr, a, i, op+1), op + a.length -1 - i);

在这种情况下，您不需要记忆：count 函数仅遵循一种方式，始终增加其内部值。

注意：我假设这里的鱼已经排序，如您的代码中所述。

复杂度，不考虑排序：O(n + log(weight_max/weigth_in))

编辑：还有另一种方法可以加快这个过程：

如果在给定时间，操作次数op大于当前最佳值，则可以停止递归。

Answer 3

正如其他人回答的那样，贪心可以在这里工作。在第一次吃掉所有较小的鱼后，每个选择点是（1）添加比当前饥饿鱼小的最大可能鱼，或（2）移除所有相等或更大的鱼。显然，从中间取出一条鱼是不必要的，因为如果我们可以吃掉更大的一条，我们也可以吃掉那条。

我们要优化的状态是num_current_moves + num_removals_needed。但是因为我们只需要一个变量来存储最好看到的状态，我们可以在每次选择后更新它，迭代排序列表，贪婪地添加鱼。选项 (2) 不是主动更改；相反，它只是计算每个点的最佳可见状态的一部分。

迭代JavaScript代码：

function f(x, A){
  A.sort((a, b) => a - b)
  
  let sum = x
  let removals_needed = A.length
  let moves = 0
  let best = removals_needed
  let i = 0
  
  while (i < A.length){
    if (sum > A[i]){
      sum = sum + A[i]
      removals_needed = removals_needed - 1
      i = i + 1

    // It might not be worth
    // trying to grow the fish,
    // but the growth rate is 
    // probably fast enough not
    // to add significant time
    } else {
      sum = sum + (sum - 1)
      moves = moves + 1
    }
    
    best = Math.min(best, moves + removals_needed)
  }
  
  return best
}

var inputs = [
  [10, [9,20,25,100]], // 2
  [3, [25,20,100,400,500]], // 5
  [3, [20,21,22,23,24,25]], // 4
  [3, [20,21,22]], // 3
  [50, [25,20,9,100]] // 0
]

for (let [x, A] of inputs){
  console.log(`${x} -> ${A}`)
  console.log(f(x, A))
  console.log("")
}

Answer 4

public static int HungryFish(int infectedFishSize, int[] fishs)
    {
        Array.Sort(fishs);
        int moves = 0;

        for (int i = 0; i < fishs.Length; i++)
        {
            if (fishs[i] < infectedFishSize)
            {
                infectedFishSize += fishs[i];
            }
            else
            {
                if (fishs[i] < (infectedFishSize + infectedFishSize - 1))
                {
                    infectedFishSize += (infectedFishSize - 1);
                    moves++;
                }
                else
                {
                    moves += (fishs.Length - i);
                    break;
                }
            }
        }

        return moves;
    }

受感染的鱼可以吃掉比自己小的鱼。所需的最少操作次数

Infected Fish can eat another fish having size less that its own. Minimum number of operation required

algorithm

dynamic-programming

data-structures

array-algorithms